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

看来我略过了“在这个例子中 [1, 5] 是根:”位，因此使我之前的答案变得相当复杂。标准有向图和Breadth-first search修改路径查找即可完成这项工作。

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]) 作为要扩展的下一个节点。我将再次将路径查找算法作为练习。