gpt4 book ai didi

python - 将一次取 m 个点的所有可能组合分组为 r 个组

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:01:21 24 4
gpt4 key购买 nike

我想将一次 m 点的所有可能组合分为 r 组。

Points = [A,B,C,D........] Total n points

一次 m 这些点的组合将是一个列表 l

l = list(itertools.combinations(points,m))

我怎样才能进一步将它分成 r 组,使得每个组的 i-th 元素没有相似点。

例如,

Points = [A,B,C,D] m = 2 and r = 2

l = [[A,B],[A,C],[A,D],[B,C],[B,D],[C,D]]

所以群体会是

Group 1 = [[A,B],[A,C],[A,D]] and corresponding to it Group 2 = [[C,D],[B,D],[B,C]]

注意:第1组和第2组的第i个索引中的点没有相似点。

我想对 n 个点进行一次 m 并将其分为 r 组。

请提供算法。

另请注意,当点数增加时,如果我们想要超过 2 组,则可能的组合也会增加。

最佳答案

这是一个棘手的问题!我已经实现了一个天真的蛮力解决方案。这可能太慢了,但它是一个起点。

from itertools import combinations, permutations

points = 'ABCDEF'
r = 3
m = len(points) // r
all_combinations = list(combinations(points, m))
group_length = len(all_combinations) // r
assert r * group_length == len(all_combinations)
found = set()

for combinations_permutation in permutations(all_combinations):
groups = [combinations_permutation[group_length * i: group_length * (i + 1)]
for i in range(r)]
transpose = zip(*groups)

# Avoid very similar-looking solutions
canonical = frozenset(map(frozenset, transpose))

if (canonical not in found and
all(len(col) == len(set(col))
for col in (sum(column, ()) for column in transpose))):
found.add(canonical)
for group in groups:
print ', '.join(map(''.join, group))
print '----'

这是输出的开始:

AB, AC, AD, AE, AF
CD, BE, BF, BD, BC
EF, DF, CE, CF, DE
----
AB, AC, AD, AE, AF
CD, BF, BE, BC, BD
EF, DE, CF, DF, CE
----
AB, AC, AD, AE, AF
CE, BD, BE, BF, BC
DF, EF, CF, CD, DE
----
AB, AC, AD, AE, AF
CE, BF, BC, BD, BE
DF, DE, EF, CF, CD

关于python - 将一次取 m 个点的所有可能组合分组为 r 个组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37501900/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com