python - 枚举所有可能的二人组星座

Question

我正在寻找一种方法来为 n 个成员枚举所有可能的双成员组群。

例如，对于 n = 4 名成员，可能有以下 3 个独特的组群(请注意，组内成员的顺序和组顺序都不重要):

((1,2), (3,4))
((1,3), (2,4))
((1,4), (2,3))

例如，对于 n = 6 个成员，可能有 15 个独特的星座:

((1,2), (3,4), (5,6))
((1,2), (5,4), (3,6))
((1,2), (6,4), (5,3))
((1,3), (2,4), (5,6))
((1,3), (2,6), (5,4))
((1,3), (2,5), (4,6))
((1,4), (3,2), (5,6))
((1,4), (3,5), (2,6))
((1,4), (3,6), (5,2))
((1,5), (3,4), (2,6))
((1,5), (3,2), (4,6))
((1,5), (3,6), (2,4))
((1,6), (3,4), (5,2))
((1,6), (3,5), (2,4))
((1,6), (3,2), (5,4))

对于 n 个成员，唯一组的数量可以计算为

choose(n,2)*choose(n-2,2)*...*choose(2,2)/factorial(n/2),

其中 choose(n,k) 是二项式系数。

对于 n = 4 我们有

choose(4,2)/factorial(4/2) = 3 

可能的二人组星座。对于 n = 6，它是

choose(6,2)*choose(4,2)/factorial(6/2) = 15. 

对于超过 n = 6 的成员，手动枚举组是不可行的。有没有一种简单的方法来获取包含所有可能的组群的列表/数据框？

Answer 1

这看起来可行:

from itertools import combinations, islice

def cons(nums):
    if len(nums)%2 or len(nums)<2:
        raise ValueError
    if len(nums) == 2:
        yield (nums,)
        return
    for c in islice(combinations(nums, 2), len(nums)-1):
        for sub in cons(tuple(set(nums) - set(c))):
            yield ((c,) + sub)

def constellations(n):
    return cons(range(1, n+1))

for c in constellations(6):
    print c

输出:

((1, 2), (3, 4), (5, 6))
((1, 2), (3, 5), (4, 6))
((1, 2), (3, 6), (4, 5))
((1, 3), (2, 4), (5, 6))
((1, 3), (2, 5), (4, 6))
((1, 3), (2, 6), (4, 5))
((1, 4), (2, 3), (5, 6))
((1, 4), (2, 5), (3, 6))
((1, 4), (2, 6), (3, 5))
((1, 5), (2, 3), (4, 6))
((1, 5), (2, 4), (3, 6))
((1, 5), (2, 6), (3, 4))
((1, 6), (2, 3), (4, 5))
((1, 6), (2, 4), (3, 5))
((1, 6), (2, 5), (3, 4))

根据公式为 constellations(8) 生成 105 个条目。
本质上，我所做的只是获取第一个元素与其他元素的组合，然后将其余元素传递给递归——这确保没有重复的组。