列举所有可能的两个成员组星座

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

其中,选择(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))

生成 105 个条目，并constellations(8)根据公式进行检查。
本质上，我所做的只是获取第一个元素与每个其他元素的组合，然后将剩余部分传递到递归中——这确保了没有重复的组。