我有一个像这样的不寻常的树数组:
[[0, 1], [1, 2], [2, 3], [2, 4], [2, 5], [5, 6],
[4, 6], [3, 6], [0, 7], [7, 6], [8, 9], [9, 6]]
数组的每个元素都是一对,这意味着第二个元素是第一个的跟随者,例如:
[0, 1] - 0 is followed by 1
[1, 2] - 1 is followed by 2
我试图提取这样的数组:
0 1 2 3 6
0 1 2 4 6
0 1 2 5 6
0 7 6
8 9 6
我无法编写强大的遍历来提取所有可能的路径.我怎么能用Python做到这一点?
解决方法:
干得好.不是地球上最好的代码,但它有效:
inputValues = [[0, 1], [1, 2], [2, 3], [2, 4], [2, 5], [5, 6], [4, 6], [3, 6], [0, 7], [7, 6], [8, 9], [9, 6]]
tree = {}
numberOfChildren = {}
for (f, t) in inputValues:
if not tree.has_key(f):
tree[f] = []
tree[f].append(t)
if not numberOfChildren.has_key(t):
numberOfChildren[t] = 0
numberOfChildren[t] += 1
roots = [c for c in tree if c not in numberOfChildren]
permutations = []
def findPermutations(node, currentList):
global tree
global permutations
if not tree.has_key(node):
permutations.append(currentList)
return
for child in tree[node]:
l = list()
l.extend(currentList)
l.append(child)
findPermutations(child, l)
for r in roots:
findPermutations(r, [r])
print permutations