我有一个圆增长算法(带闭合链接的线增长),其中在每次迭代时在现有点之间添加新点。
每个点的链接信息以元组的形式存储在列表中。该列表会迭代更新。
问题:
将这些点的空间顺序作为列表返回的最有效方法是什么?
我是否需要在每次迭代时计算整个顺序,或者有没有办法以有序的方式将新点累积插入到该列表中?
我能想到的是以下内容:
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)
最佳答案
与递归相比,这对我来说更像是一个字典和生成器问题:
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
%
算法目前假定我们有两个以上的节点。
关于python - 从元组列表中查找空间顺序的最有效方法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54245191/