Python：从树状数据结构的列表中创建组合

Question

我有一个包含 n 对数字的列表，每对数字的范围在1到70之间。

aList = [[1, 5], [1, 12],...,[5, 45], [5, 47],...,[45, 49], [45, 65], ...]

这个列表中的每一对数字都可以看作是树的根，而组合就是从这个根开始构建的。

在这个例子中，[1, 5] 是根：

#                    [45, 65]
#             [5,45]/           [y, k]--...
#            /      \[45,49]   /
#           |                 |
# root: [1,5]--[5, x] -- [x, y]--[y,z]--...
#           |                 |
#            \      /[47,?]    \
#             [5,47]            [y, j]--...
#                   \[47,?]

我想要从这些对数字中创建组合，前提是 n[1] == n+1[0]。

举个例子：

[1,5,45,49,...]
[1,5,45,65,...]
[1,5,47,x,y,k,...]
[1,5,47,x,y,z,...]
[1,5,47,x,y,j,...]
[1,5,47,?,...]
[1,5,47,?,??]

我试过使用 itertools.product，但它会生成所有可能的组合。

提前谢谢你。

Answer 1

谢谢你，Nuclearman，你的回答帮我想出了一个解决办法。

这个方法有点粗糙，我相信还有更优雅的写法，但对我来说已经足够用了。

def treeSearch(i):
     if i in graph.keys():
         return graph[i]
     else:
         return [0]

edges = aList
graph = {}
for a,b in edges:
    if a not in graph.keys():
        graph[a] = []
        for c,d in edges:
           if a == c:
               graph[a].append(d)

for key in graph:
    for k in graph[key]:
        for j in treeSearch(k):
            for h in treeSearch(j):
                for g in treeSearch(h):
                    for f in treeSearch(g):
                        for v in treeSearch(f):
                            print [key,k,j,h,g,f,v]

Answer 2

看起来我之前有点儿忽略了“在这个例子中，[1, 5]是根节点”这部分内容，所以把我的回答搞得有点复杂了。其实，标准的有向图和广度优先搜索，经过一些修改后就可以用来找路径了。

def directed_graph_from_edges(edges):
    graph = {}
    for a,b in edges:
        graph.setdefault(a,set())
        graph[a].add(b)
    return graph

这个路径寻找算法只需要把一条边作为输入，而不是单个的节点。不过，它仍然会把路径中的最后一个节点（last_vertex = path[-1]）当作下一个要扩展的节点。再次提醒，路径寻找的算法我就留给大家自己去练习了。