所有可能的两人组星座的枚举

Question

我正在寻找一种方法来枚举n个成员的所有可能的两个成员组星座。在

例如，对于n=4个成员，可以使用以下3个唯一的组星座（请注意，组内成员的顺序和组顺序都不重要）：

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

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

^{pr2}$

对于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

输出：

^{pr2}$

为constellations(8)生成105个条目，该条目根据公式签出。
本质上，我要做的是只获取第一个元素和其他元素的组合，然后将剩余的元素传递到递归中——这可以确保没有重复的组。在

Answer 2

如果要将1:n的所有分区枚举为对，可以递归地进行。 这是一个R解。在

f <- function(x) {
  # We can only partition the set into pairs 
  # if it has an even number of elements
  stopifnot( length(x) %% 2 == 0 )
  stopifnot( length(x) > 0 )
  # To avoid double counting, sort the array, 
  # and put the first element in the first pair
  x <- sort(x)
  # The first pair contains the first element 
  # and another element: n - 1 possibilities
  first_pairs <- lapply( x[-1], function(u) c(x[1],u) )
  if( length(x) == 2 ) { return( list( first_pairs ) ) }
  # Progressively build the result, by considering 
  # those pairs one at a time
  result <- list()
  for( first_pair in first_pairs ) {
    y <- setdiff( x, first_pair )
    rest <- f(y)
    # Call the function recursively: 
    # a partition of 1:n that starts with (1,2)
    # is just (1,2) followed by a partition of 3:n.
    result <- append( 
      result, 
      # This is the tricky bit: 
      # correctly use append/c/list to build the list.
      lapply( rest, function (u) { append( list( first_pair ), u ) } )  
    )
  }
  result
}

# The result is a list of lists of 2-element vectors: print it in a more readable way.
result <- f(1:6)
result <- lapply( result, function (u) unlist(lapply( u, function (v) paste( "(", paste(v,collapse=","), ")", sep="" ))))
result <- unlist( lapply( result, function (u) paste( u, collapse=", " ) ) )