从元组列表中找到空间顺序的最有效方法是什么？

Question

我有一个圆形增长算法（具有闭合链接的线性增长），每次迭代都会在现有点之间添加新点。

每个点的关联信息存储在列表中的元组中。该列表进行迭代更新。

问题：

• 以列表形式返回这些点的空间顺序，最有效的方法是什么？

• 我是否需要在每次迭代时计算整个顺序，还是有一种方式可以按顺序将新点累加地插入到该列表中？

我能想到的唯一方法如下：

tuples = [(1, 4), (2, 5), (3, 6), (1, 6), (0, 7), (3, 7), (0, 8), (2, 8), (5, 9), (4, 9)]

starting_tuple = [e for e in tuples if e[0] == 0 or e[1] == 0][0]
## note: 'starting_tuple' could be either (0, 7) or (0, 8), starting direction doesn't matter

order = list(starting_tuple) if starting_tuple[0] == 0 else [starting_tuple[1], starting_tuple[0]]
## order will always start from point 0


idx = tuples.index(starting_tuple)
## index of the starting tuple


def findNext():
    global idx
    for i, e in enumerate(tuples):
        if order[-1] in e and i != idx:
            ind = e.index(order[-1])
            c = 0 if ind == 1 else 1
            order.append(e[c])
            idx = tuples.index(e)


for i in range(len(tuples)/2):
    findNext()

print order

它可以工作，但既不优雅（非Pythonic），也不高效。 我认为递归算法可能更合适，但不幸的是我不知道如何实现这样的解决方案。

另外，请注意我正在使用Python 2，并且只能访问完整的Python包（没有numpy）。

- solub

---

如果您的代码已经正常运行，但您正在寻求改进建议，我建议您查看Code Review，他们专注于突出改进的领域。 - Jab

@Jaba 谢谢建议。 - solub

同样在你的第三行代码中，你可以将order = [starting_tuple[0], starting_tuple[1]]替换为order = list(starting_tuple)。 - Jab

如果起始元组是(7, 0)或(8, 0)之一，那会怎样？这种情况可能发生吗？它会不会破坏你最初的假设？ - cdlane

@cdlane 两个元组都是有效的起始方向。脚本应该可以正常工作。 - solub

Answer 1

由于节点只链接到另外两个节点，您可以按编号对它们进行分组，然后按照编号顺序遍历。这是O(n)排序，相当可靠，但它不是真正的<,>,=排序。

def bin_nodes(node_list):
    #figure out the in and out nodes for each node, and put those into a dictionary.
    node_bins = {} #init the bins
    for node_pair in node_list: #go once through the list
        for i in range(len(node_pair)): #put each node into the other's bin
            if node_pair[i] not in node_bins: #initialize the bin dictionary for unseen nodes
                node_bins[node_pair[i]] = []
            node_bins[node_pair[i]].append(node_pair[(i+1)%2])
    return node_bins

def sort_bins(node_bins):
    #go from bin to bin, following the numbers
    nodes = [0]*len(node_bins) #allocate a list
    nodes[0] = next(iter(node_bins)) #pick an arbitrary one to start
    nodes[1] = node_bins[nodes[0]][0] #pick a direction to go
    for i in range(2, len(node_bins)):
        #one of the two nodes in the bin is the horse we rode in on.  
        #The other is the next stop.   
        j = 1 if node_bins[nodes[i-1]][0] == nodes[i-2] else 0 #figure out which one ISN"T the one we came in on
        nodes[i] = node_bins[nodes[i-1]][j] #pick the next node, then go to its bin, rinse repeat
    return nodes

if __name__ == "__main__":
    #test
    test = [(1,2),(3,4),(2,4),(1,3)] #should give 1,3,4,2 or some rotation or reversal thereof
    print(bin_nodes(test))
    print(sort_bins(bin_nodes(test)))

- Him

---

有趣的建议。您介意简要解释一下这种解决方法比我提供的更有效吗？ - solub

你的for循环是线性的，然后循环内的.index操作也是线性的。这使得运行时间呈现二次方增长。基本上就是插入排序。 - Him

Answer 2

与其使用递归，我认为这更像是一个字典和生成器的问题：

from collections import defaultdict

def findNext(tuples):
    previous = 0
    yield previous  # our first result

    dictionary = defaultdict(list)

    # [(1, 4), (2, 5), (3, 6), ...] -> {0: [7, 8], 1: [4, 6], 2: [5, 8], ...}
    for a, b in tuples:
        dictionary[a].append(b)
        dictionary[b].append(a)

    current = dictionary[0][0]  # dictionary[0][1] should also work
    yield current  # our second result

    while True:
        a, b = dictionary[current]  # possible connections

        following = a if a != previous else b  # only one will move us forward

        if following == 0:  # have we come full circle?
            break

        yield following  # our next result

        previous, current = current, following  # reset for next iteration

tuples = [(1, 4), (2, 5), (3, 6), (1, 6), (7, 0), (3, 7), (8, 0), (2, 8), (5, 9), (4, 9)]

generator = findNext(tuples)

for n in generator:
    print n

输出

% python test.py
0
7
3
6
1
4
9
5
2
8
% 

该算法目前假设我们有两个以上的节点。

- cdlane

---

优雅的解决方案，巧妙地利用生成器。谢谢。 - solub