在特定条件下生成边的组合

Question

我将图的边表示为 (node_from, node_to).

我想有效地生成形式为 (0,x) 的两条边的所有组合，其中 0 是我图中的节点 0 - 结合形式为 (x,n) 的两条边的所有组合，其中 n 是我图表中的 "final node" （我知道是任意的）。我已经将所有边放在一个集合中，或者每个节点都包含到每个其他节点的边（例如，您可以直接遍历范围以生成组合）。

有效组合可以是

(0,1),(0,5),(7,n),(11,n) 或
(0,1),(0,5),(5,n),(11,n) 或
(0,1),(0,n),(0,n),(11,n)

并且，为了清楚起见，我想要组合而不是排列。我不想重复使用同一个组。

我通常很擅长解决这些问题，但我在这方面遇到了一些麻烦。

Answer 1

编辑：更新以适应"only two start/end edges"

的要求

我不确定你想到的是什么接口，但据我了解，你可以使用 filter() 到 select "start in 0" 或 "start in 0" 的边缘子集"end in 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()来生成"pair from one list"和"pair from other list"的所有组合：

>>> 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))

就是这样！如果你愿意，你可以 "flatten" 数据结构，但这是可选的：

>>> 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

python

algorithm

combinations

combinatorics