枚举所有可能的双成员群星座

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

可生产105个条目constellations(8)根据下式，其检查出来。
本质上，我正在做的只是抓住第一个元素与其他元素的组合，然后将其余部分传递给递归 - 这确保没有重复的组。

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

Answer 3

我想出了：

from itertools import combinations 

def have_common(a, b): 
    """Test if two iterables have a common item.""" 
    for i in a: 
     if i in b: 
      return True 
    return False 

def have_same(iterable): 
    """Test if a nested iterable like ((1, 2), (3, 4), (5, 6)) 
    present the same number more then once. 

    """ 
    memory = [] 
    for duo in iterable: 
     if have_common(memory, duo): 
      return True 
     else: 
      memory.extend(duo) 
    return False 

def constellation(num): 
    """Loops on all the combinations of 2 combinations and then yields them 
    if they don't have numbers in common. 

    """ 
    lst = (i for i in combinations(range(1, num+1), 2)) 
    for cost in combinations(lst, int(num/2)): 
     if not have_same(cost): 
      yield cost 

运行：

for i in constellation(6): 
    print(i) 

我：

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

性能：这仍然可以更好地改善算法为have_same和have_common。

但我做了一点时间反正有timit和我：

constellation(4): 13.54 usec/pass 
constellation(6): 118.48 usec/pass 
constellation(8): 3222.14 usec/pass 

Answer 4

包partitions写回答像你这样的，它（数学术语）是关于枚举所有可能的六partitions of a set问题将R元素分成两个元素的三个等价类。

该软件包提供了两个功能 - setparts()和listParts() - 将枚举所有分区。这些功能仅在返回这些结果的格式上有所不同。

在这里，我向listParts()函数的输出，主要是因为它返回的打印格式是更接近你包含在原来的问题是什么：

library(partitions) 
    P <- listParts(c(2,2,2)) 
    N <- sapply(P, print) 
    # [1] (1,6)(2,5)(3,4) 
    # [1] (1,6)(2,4)(3,5) 
    # [1] (1,6)(2,3)(4,5) 
    # [1] (1,2)(3,6)(4,5) 
    # [1] (1,2)(3,5)(4,6) 
    # [1] (1,2)(3,4)(5,6) 
    # [1] (1,3)(2,6)(4,5) 
    # [1] (1,3)(2,4)(5,6) 
    # [1] (1,3)(2,5)(4,6) 
    # [1] (1,4)(2,6)(3,5) 
    # [1] (1,4)(2,5)(3,6) 
    # [1] (1,4)(2,3)(5,6) 
    # [1] (1,5)(2,6)(3,4) 
    # [1] (1,5)(2,4)(3,6) 
    # [1] (1,5)(2,3)(4,6)