在Python中创建渐进列表迭代

Question

我有一个包含多条线段的列表，这些线段组成了多个形状，比如正方形、矩形等等。不过这些线段是分开的，我想找个办法把它们按形状分成不同的列表。举个例子，如果我的列表里有8条线段，而我知道它们可以组成两个矩形，我就想把它们分成两个各有四条线段的组。

现在，我可以查询每条线段的起点和终点。我在想，能不能设置一个循环，逐条检查这个列表。首先选取列表中的第一条线段，获取它的终点，然后检查这个终点是否和列表中其他线段的起点相等。如果相等，就把那条线段加入到与第一条线段同一组里。接着再拿这第二条线段，重复这个过程，直到某条线段的起点等于最后一条线段的终点，并且第一条线段的起点等于它的终点为止。

我该怎么做呢？

lines = [line1, line2, line3, line4, line5, line6, line7] #that means i have a square and a triangle
for i in lines:
    shape1.append(lines[0])
    sPoint = lines[0].StartPoint()
    ePoint = lines[0].EndPoint()
    if i.StartPoint() == ePoint:
        shape1.append(i)

我不太确定怎么自动创建“形状”列表，也不知道怎么打破循环，以免陷入无休止的循环中。

任何帮助都非常感谢。谢谢！

Answer 1

就像@ChristophHegemann提到的那样，想象一下数字其实只是用来表示点的。所以在我的例子中，Line(1,4)或者Edge(1,4)其实就是在点1和点4之间画一条线。

from pprint import pprint

class Edge(object):
    def __init__(self,a,b):
        self.a        = a
        self.b        = b
        self.previous = None
        self.next     = None

    def __repr__(self):
        return "<Edge(%s,%s)>" % (self.a,self.b)

def find_shapes(lines):
    # builds the graph
    lines  = link_lines(lines)
    # explores the graph
    shapes = extract_shapes(lines)
    return shapes    

def link_lines(lines):
    # keep a safe copy of the list of lines. The original list will be tampered with.
    lines_copy = list(lines)

    for L in lines_copy:
        lines.remove(L)
        for line in lines:
            # if current line's end is other line's start
            if L.b == line.a:
                L.next        = line
                line.previous = L

            # if current line's start is other line's end
            elif L.a == line.b:
                L.previous = line
                line.next  = L

            # if we found both the previous and the next edge then we're done for this edge.
            # (edge has at most 1 previous and 1 next edge in a given shape).
            # this of course supposes that any single edge is present in at most one shape.

            if L.previous and L.next :
                break

        #put L back in
        lines.append(L)

    # return newly linked lines (graph)
    return lines

def extract_shapes(lines):
    lines_copy = list(lines)
    shapes     = []
    while lines_copy : 
        L         = lines_copy.pop()
        shape     = [L]
        next_edge = L.next
        # unlike @ChristophHegemann I work with edges, but the algorithm seems 
        # to be the same whether you work with edges or vertices
        while next_edge != L:
            shape.append(next_edge)
            lines_copy.remove(next_edge)            
            next_edge = next_edge.next

        shapes.append(shape)
    return shapes

# list of lines
# let's pretend shapes are : L1,L10,L2,L4 and L5,L3,L7,L11 and L6,L9,L8,L12

L1  = Edge(1,2)
L10 = Edge(2,3)
L2  = Edge(3,4)
L4  = Edge(4,1)

L5  = Edge(5,6)
L3  = Edge(6,7)
L7  = Edge(7,8)
L11 = Edge(8,5)

L6  = Edge(9,10)
L9  = Edge(10,11)
L8  = Edge(11,12)
L12 = Edge(12,9)

# random order of lines 
lines = [L1,L2,L3,L4,L5,L6,L7,L8,L9,L10,L11,L12]

pprint(find_shapes(lines))

# chaouche@karabeela ~/CODE/TEST/PYTHON/SO $ python lines.py
# [[<Edge(12,9)>, <Edge(9,10)>, <Edge(10,11)>, <Edge(11,12)>],
#  [<Edge(8,5)>, <Edge(5,6)>, <Edge(6,7)>, <Edge(7,8)>],
#  [<Edge(2,3)>, <Edge(3,4)>, <Edge(4,1)>, <Edge(1,2)>]]
# chaouche@karabeela ~/CODE/TEST/PYTHON/SO $

Answer 2

这不是最好的算法，但我有点困，这个应该能让你入门：

lines = [line1, line2, line3, line4, line5, line6, line7]
shapes = []

while lines:
    shape = [lines[0]]
    i=1
    while i < len(lines):
        line1 = lines[i]
        for line2 in lines[i+1:]:
            if line2.start == line1.end or line2.end == line1.start or \
               line2.start == line1.start or line2.end == line1.end:

                shape.append(line2)
                lines.pop(i)
                i -= 1
                if line2.end == shape[0].start or line2.start == shape[0].end or \
                   line2.end == shape[0].end or line2.start == shape[0].start:

                    shapes.append(shape)
                    shape = []
        i += 1

要改进这个算法，可以尝试先把每一行的起点和终点排序，然后再用二分查找来找到可以连接的线。

Answer 3

前言

首先，我们定义一个 line 类，这个类包含两个点的坐标：

import itertools
import random

class line(object) :
    """
    A line has 2 ends.
    """
    def __init__(self, tup0, tup1 ) :
        self.tup0 = tup0
        self.tup1 = tup1

    def __repr__( self ) :
        return "line[{0}, {1}]".format( self.tup0, self.tup1 )

    def StartPoint(self) :
        return self.tup0

    def EndPoint(self):
        return self.tup1

    def reverseLine(self) :
        return line( self.tup1, self.tup0 )

解决方案

我会列举所有可能的形状（无论是否有效），直到找到两个封闭的形状为止：

• 我会列出所有可能的两种方式来划分这组线条
• 每个划分中的一组线条就是一个可能的形状。为了验证这一点，我会列出这组线条的所有可能排列（以及每条线的端点的所有可能顺序）
• 一旦我找到一个符合我们标准的划分（也就是说，每组都是一个封闭的形状），我就会打印出结果并停止

这里是一些辅助函数：

def is_closed( lines ) :
    """
    Return True if lines represents a closed shape (i.e., order matters)
    """
    are0ToNConnected = all( l.tup1 == lines[i+1].tup0 for i,l in enumerate( lines[:-1] ) ) 
    areFirstAndLastConnected = ( lines[-1].tup1 == lines[0].tup0 )
    return are0ToNConnected and areFirstAndLastConnected

def is_any_closed( lines ) :
    """
    Return True if at least one re-ordering of lines represents a closed shape (i.e., order doesnt matter)
    """
    return any( is_closed(newLines) 
               for permutedLines in itertools.permutations( lines ) 
               for newLines in itertools.product( * [ ( l, l.reverseLine() ) for l in permutedLines ] ) )

def k_way_partition( A, k ) :
    """
    Generator for all k-way partitions of A
    """
    if k == 1 :
        yield [ A ]
    elif len(A) == k :
        yield [ [ a ] for a in A ]
    else :
        for partition in k_way_partition( A[1:], k ) : # add new element to one of the current clusters
            for i, cluster in enumerate( partition ) :
                yield partition[:i] + [ cluster + [ A[0] ] ] + partition[i+1:]
        for partition in k_way_partition( A[1:], k-1 ) : # add new element to a new cluster
            yield [ [ A[0] ] ] + partition

这是主要的函数：

def find_shapes( lines, k ) :
    """
    Looks for a partition of lines into k shapes, and print the solution if there is one.
    """
    for partition in k_way_partition( lines, k ) :
        if all( is_any_closed(cluster) for cluster in partition ) : # we found a solution
            for j, cj in enumerate( partition ) :
                print "shape {}: {}".format(j, cj )
            break

示例

让我们生成一些随机数据并尝试这个解决方案：

# square
lines = [ line( (0,0), (0,1) ) ]
lines.append( line( (0,1), (1,1) ) )
lines.append( line( (1,1), (1,0) ) )
lines.append( line( (1,0), (0,0) ) )
# triangle
lines.append( line( (2,2), (2,3) ) )
lines.append( line( (2,3), (3,2) ) )
lines.append( line( (3,2), (2,2) ) )
lines

random.shuffle( lines )  # randomize the order of lines
for i, l in enumerate( lines ) :
    if random.random() < 0.5 :
        lines[i] = l.reverseLine()  # randomize order of coordinates
lines

输出结果：

[line[(0, 1), (1, 1)],
 line[(1, 1), (1, 0)],
 line[(2, 2), (2, 3)],
 line[(0, 0), (1, 0)],
 line[(3, 2), (2, 2)],
 line[(3, 2), (2, 3)],
 line[(0, 0), (0, 1)]]

现在让我们在随机数据上运行我们的解决方案：

find_shapes( lines, 2 )
shape 0: [line[(3, 2), (2, 3)], line[(3, 2), (2, 2)], line[(2, 2), (2, 3)]]
shape 1: [line[(0, 0), (0, 1)], line[(0, 0), (1, 0)], line[(1, 1), (1, 0)], line[(0, 1), (1, 1)]]

成功了！

Answer 4

如果你花点时间抽象一下你的问题，你会发现其实你在做的就是图。

图由顶点和边组成。顶点就是你的起点和终点。

我写了一段代码，可以帮助你解决问题，只要你明白如何把你的数据转换成建议的格式。

注释：

我建议你在阅读我的代码时，了解一下内置类型 set()。

vertices = set(['A', 'C', 'B', 'E', 'D', 'G', 'F'])

#think of this as Line1.StartPoint()='A' Line1.EndPoint()='B' ... 
edges = {'A': 'B',
         'B': 'C',
         'C': 'D',
         'D': 'A',
         'E': 'F',
         'F': 'G',
         'G': 'E'}

shapes = set()

#Check if we tested all edges
while len(vertices) is not 0:
    next = vertices.pop()
    shape = set()
    while next not in shape:
        shape.add(next)
        next = edges[next]
    shapes.add(frozenset(shape))

print shapes

结果是：

>>set([frozenset(['A', 'C', 'B', 'D']), frozenset(['E', 'G', 'F'])])

补充：虽然可以实现更快的速度，但为了简单起见，这里没有提到。