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

2024-03-28 23:11:21 发布

您现在位置:Python中文网/ 问答频道 /正文

我把一个图的边表示为(node\ u from,node\ u to)。你知道吗

我想有效地生成形式(0,x)的2条边的所有组合,其中0是我的图中的节点0-与形式(x,n)的2条边的所有组合一起,其中n是我的图中的“最终节点”(我知道是任意的)。我已经在一个集合中有了所有的边,或者每个节点都包含一个到其他节点的边(例如,您可以直接遍历范围来生成组合)。你知道吗

一个有效的组合可能是

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

我想说清楚,我想要的是组合而不是排列。我不想重复使用同一组。你知道吗

我一般都很擅长弄清楚这件事,但我在这件事上有点麻烦。你知道吗


Tags: tofromnode节点形式条边
1条回答
网友
1楼 · 发布于 2024-03-28 23:11:21

编辑:更新以满足“只有两个开始/结束边缘”的要求

我不确定您想使用什么接口,但据我所知,您可以使用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)]]

相关问题 更多 >