枚舉所有可能的雙成員羣星座

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)