在特定条件下生成边的组合
我有一个图表的边（node_from，node_to）。
我想要高效地生成形式（0，x）的2条边的所有组合，其中0是我图中的节点0，并结合形式（x，n）的2条边的所有组合，其中n是“最终节点“（任意我知道）在我的图中。 我已经将所有边缘放在一个集合中，或者每个节点都包含一个到其他节点的边缘（例如，您可以直接遍历该范围以生成组合）。
有效的组合可能是
而且，为了说清楚，我想要的组合不是排列组合。 我不想重复使用同一组。
我通常很擅长处理这些问题，但我在这方面遇到了一些麻烦。
编辑 ：更新到acommodate的要求“只有两个开始/结束边缘”
我不确定你有什么界面，但从我的理解看来，你可以使用filter()来选择“从0开始”或“以n结尾”的边缘子集。
>>> edges = [(0,1), (0,5), (0,2), (5,3), (2,9), (4,6), (6,9), (3,9), (0,9)]
>>> edges_start = filter(lambda e: e[0] == 0, edges)
>>> edges_end = filter(lambda e: e[1] == 9, edges)
>>> edges_end
[(2, 9), (6, 9), (3, 9), (0, 9)]
>>> edges_start
[(0, 1), (0, 5), (0, 2), (0, 9)]
现在可以使用itertools.combinations()从每个列表中生成所有可能的对。 这是一个例子：
>>> import itertools
>>> list(itertools.combinations(edges_start, 2))
[((0, 1), (0, 5)), ((0, 1), (0, 2)), ((0, 1), (0, 9)), ((0, 5), (0, 2)), ((0, 5), (0, 9)), ((0, 2), (0, 9))]
现在，您可以插入itertools.product()以生成“来自一个列表的对”和“来自其他列表的对”的所有组合：
>>> edges_start_pairs = list(itertools.combinations(edges_start, 2))
>>> edges_end_pairs = list(itertools.combinations(edges_end, 2))
>>> pairs = list(itertools.product(edges_start_pairs, edges_end_pairs))
而已！ 如果你喜欢，你可以“扁平化”数据结构，但这是可选的：
>>> flat_pairs = [list(p[0]+p[1]) for p in pairs]
现在让我们打印结果：
>>> from pprint import pprint
>>> pprint(flat_pairs)
[[(0, 1), (0, 5), (2, 9), (6, 9)],
[(0, 1), (0, 5), (2, 9), (3, 9)],
[(0, 1), (0, 5), (2, 9), (0, 9)],
[(0, 1), (0, 5), (6, 9), (3, 9)],
[(0, 1), (0, 5), (6, 9), (0, 9)],
[(0, 1), (0, 5), (3, 9), (0, 9)],
[(0, 1), (0, 2), (2, 9), (6, 9)],
[(0, 1), (0, 2), (2, 9), (3, 9)],
[(0, 1), (0, 2), (2, 9), (0, 9)],
[(0, 1), (0, 2), (6, 9), (3, 9)],
[(0, 1), (0, 2), (6, 9), (0, 9)],
[(0, 1), (0, 2), (3, 9), (0, 9)],
[(0, 1), (0, 9), (2, 9), (6, 9)],
[(0, 1), (0, 9), (2, 9), (3, 9)],
[(0, 1), (0, 9), (2, 9), (0, 9)],
[(0, 1), (0, 9), (6, 9), (3, 9)],
[(0, 1), (0, 9), (6, 9), (0, 9)],
[(0, 1), (0, 9), (3, 9), (0, 9)],
[(0, 5), (0, 2), (2, 9), (6, 9)],
[(0, 5), (0, 2), (2, 9), (3, 9)],
[(0, 5), (0, 2), (2, 9), (0, 9)],
[(0, 5), (0, 2), (6, 9), (3, 9)],
[(0, 5), (0, 2), (6, 9), (0, 9)],
[(0, 5), (0, 2), (3, 9), (0, 9)],
[(0, 5), (0, 9), (2, 9), (6, 9)],
[(0, 5), (0, 9), (2, 9), (3, 9)],
[(0, 5), (0, 9), (2, 9), (0, 9)],
[(0, 5), (0, 9), (6, 9), (3, 9)],
[(0, 5), (0, 9), (6, 9), (0, 9)],
[(0, 5), (0, 9), (3, 9), (0, 9)],
[(0, 2), (0, 9), (2, 9), (6, 9)],
[(0, 2), (0, 9), (2, 9), (3, 9)],
[(0, 2), (0, 9), (2, 9), (0, 9)],
[(0, 2), (0, 9), (6, 9), (3, 9)],
[(0, 2), (0, 9), (6, 9), (0, 9)],
[(0, 2), (0, 9), (3, 9), (0, 9)]]
上一篇: Generating combinations of edges under a certain condition