Enumerazione di tutte le possibili costellazioni di gruppo a due membri

Question

Sto cercando un modo per enumerare tutte le possibili costellazioni di gruppo di due membri per n membri.

esempio, per n = 4 membri i seguenti 3 costellazioni gruppo uniche sono possibili (si noti che né l'ordine dei membri di un gruppo, né l'ordine gruppo è di importanza):

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

Eg, per n = 6 membri 15 costellazioni uniche possibili:

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

per n membri numero di gruppi unici può essere calcolato come

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

dove scegliere (n, k) è il coefficiente binomiale.

Per n = 4 abbiamo

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

possibili costellazioni gruppo di due componenti. Per n = 6 è

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

Un enumaration dei gruppi a mano non è fattibile per più di n = 6 membri. C'è un modo semplice per ottenere una lista/dataframe con tutte le possibili costellazioni di gruppo?

Answer 1

Questo appare come funziona:

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 

uscita:

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

Produce 105 voci per constellations(8) che controlla secondo la formula.
In sostanza, quello che sto facendo è catturare solo le combinazioni del primo elemento con ogni altro elemento, e quindi passare il resto alla ricorsione - questo non garantisce gruppi ripetuti.

Answer 2

Se si desidera enumerare tutte le partizioni di 1: n in coppie, è sufficiente eseguirlo in modo ricorsivo. Ecco una soluzione 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

mi si avvicinò con:

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 

Esecuzione:

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

ho ottenuto:

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

Performance: Questo può ancora essere migliorato con una migliore un algoritmi per have_same e have_common.

Ma ho fatto un po 'i tempi in ogni caso con timit ed ho ottenuto:

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

Answer 4

La R pacchetto partitions è stato scritto per rispondere a domande come la vostra, che (in termini matematici) è di circa l'enumerazione di tutti i possibili partitions of a set di sei elementi in tre classi di equivalenza di due elementi ciascuno.

Il pacchetto prevede due funzioni:e listParts(), che enumera tutte le partizioni. Le funzioni differiscono unicamente nel formato in cui restituiscono tali risultati.

Qui, mi mostra l'output della funzione listParts(), soprattutto perché il formato stampato che ritorna è più vicino a quello che è stato incluso nella domanda iniziale:

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)