每次从点中取m个点的所有可能组合分成r组

Question

我希望将每次取m个点的所有可能组合分成r个组。

点集 = [A,B,C,D........] 共有n个点

这些点中每次取m个点的组合将会是一个列表l

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

如何将其进一步分成r组，以使每个组的第i个元素没有相似点。

例如，

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]] 对应的 Group 2 = [[C,D],[B,D],[B,C]]

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

我想对n个点进行这样的操作，每次取m个点并将其分组为r个组。

请提供算法。

还要注意，当点数增加时，如果我们想要更多的组，则可能的组合也会增加。

- Abhishek Genva

---

这是 http://mathworld.wolfram.com/SocialGolferProblem.html 吗？ - David Eisenstat

是的，有点相似。这将帮助我解决我的问题。你能为我提供社交高尔夫问题的解决方案吗？我需要Python的算法或代码。提前致谢。 - Abhishek Genva

你尝试过用伪代码实现这个逻辑吗？请贴出来。 - wwii

David的链接明确表示问题通常是未解决的。您需要进行一些研究以了解已经发现了什么。 - Alex Hall

你说它们有点相似，但我看不出任何区别。有吗？r、m和n的限制是什么？如果它们太大了，这可能是没有希望的。此外，显然 r × m ≤ n，但是 r × m < n 可能吗？ - Alex Hall

我们需要将r x m的所有可能组合存储在n个组中。 - Abhishek Genva

Answer 1

这是一个棘手的问题！我实现了一个天真的暴力解决方案。这可能太慢了，但它是一个起点。

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

- Alex Hall