Python: Generazione di tutte le coppie pairwise-uniche

Question

Sto cercando un metodo Pythonic per generare tutti gli accoppiamenti unici unidirezionali (dove un pairing è un sistema composto da coppie, e pairwise-unique indica che (a,b) ≠ (b,a)) per un set contenente anche numero n articoli.

mi piace il codice here:

for perm in itertools.permutations(range(n)): 
    print zip(perm[::2], perm[1::2]) 

tranne che genera tutti, abbinamenti a due a due-unici order-unico, o (n/2)! volte più abbinamenti di quanto io voglio (ridondanza), che, anche se posso filtrare fuori, davvero impantanarsi il mio programma in grande n.

Cioè, per n = 4, Cerco il seguente output (12 abbinamenti unici):

[(0, 1), (2, 3)] 
[(0, 1), (3, 2)] 
[(1, 0), (2, 3)] 
[(1, 0), (3, 2)] 
[(1, 2), (0, 3)] 
[(1, 2), (3, 0)] 
[(1, 3), (0, 2)] 
[(2, 0), (1, 3)] 
[(2, 0), (3, 1)] 
[(3, 1), (0, 2)] 
[(0, 3), (2, 1)] 
[(3, 0), (2, 1)] 

noti che (a,b) ≠ (b,a).

È possibile? Sto anche bene con una funzione che genera i 3 accoppiamenti unici non-pair per n = 4 dove (a,b) = (b,a), poiché è semplice permutare ciò di cui ho bisogno da lì. Il mio obiettivo principale è evitare le permutazioni superflue nell'ordine delle coppie nell'associazione.

Grazie in anticipo per il vostro aiuto e suggerimenti, lo apprezzo molto.

Answer 1

Penso che questo ti dia gli abbinamenti fondamentali di cui hai bisogno: 1 quando N=2; 3 quando N=4; 15 quando N=6; 105 quando n=8, ecc.

import sys 

def pairings(remainder, partial = None): 
    partial = partial or [] 

    if len(remainder) == 0: 
     yield partial 

    else: 
     for i in xrange(1, len(remainder)): 
      pair = [[remainder[0], remainder[i]]] 
      r1 = remainder[1:i] 
      r2 = remainder[i+1:] 
      for p in pairings(r1 + r2, partial + pair): 
       yield p 

def main(): 
    n = int(sys.argv[1]) 
    items = list(range(n)) 
    for p in pairings(items): 
     print p 

main() 

Answer 2

Nella domanda collegato "Generazione di tutte le permutazioni unici pair", (here), un algoritmo è dato per generare un programma round-robin per qualsiasi n. Cioè, ogni possibile insieme di abbinamenti/accoppiamenti per le squadre n.

Così, per n = 4 (supponendo esclusiva), che sarebbe:

[0, 3], [1, 2] 
[0, 2], [3, 1] 
[0, 1], [2, 3] 

ora abbiamo ciascuna di queste partizioni, abbiamo solo bisogno di trovare i loro permutazioni al fine di ottenere l'elenco completo delle abbinamenti. cioè [0, 3], [1, 2] è un membro di un gruppo di quattro: [0, 3], [1, 2] (stesso) e [3, 0], [1, 2] e [0, 3], [2, 1] e [3, 0], [2, 1].

Per ottenere tutti i membri di un gruppo da un membro, si prende la permutazione in cui ciascuna coppia può essere capovolta o non capovolta (se fossero, ad esempio, n-tuple invece di coppie, quindi ci sarebbe n ! opzioni per ciascuno). Quindi, poiché hai due coppie e opzioni, ciascuna partizione produce coppie 2^2. Quindi hai 12 del tutto.

Codice per eseguire questa operazione, dove round_robin (n) restituisce un elenco di elenchi di coppie. Quindi round_robin (4) -> [[[0, 3], [1, 2]], [[0, 2], [3, 1]], [[0, 1], [2, 3]] ].

def pairs(n): 
    for elem in round_robin(n): 
     for first in [elem[0], elem[0][::-1]]: 
      for second in [elem[1], elem[1][::-1]]: 
       print (first, second) 

Questo metodo genera meno di quanto si desidera e poi sale invece di generare più di quanto si desidera e come liberarsi di un gruppo, quindi dovrebbe essere più efficiente. ([:: - 1] è un voodoo per l'inversione di una lista immutabilmente).

Ed ecco l'algoritmo round-robin dall'altra distacco (scritto da Theodros Zelleke)

from collections import deque 

def round_robin_even(d, n): 
    for i in range(n - 1): 
     yield [[d[j], d[-j-1]] for j in range(n/2)] 
     d[0], d[-1] = d[-1], d[0] 
     d.rotate() 

def round_robin_odd(d, n): 
    for i in range(n): 
     yield [[d[j], d[-j-1]] for j in range(n/2)] 
     d.rotate() 

def round_robin(n): 
    d = deque(range(n)) 
    if n % 2 == 0: 
     return list(round_robin_even(d, n)) 
    else: 
     return list(round_robin_odd(d, n)) 

Answer 3

non sono sicuro se ho capito bene il problema, in ogni caso ecco la mia soluzione:

import itertools 
n = 4 
out = set() 
for perm in itertools.permutations(range(n)): 
    pairs = tuple(sorted(zip(perm[::2], perm[1::2]))) 
    out.add(pairs) 

for i, p in enumerate(sorted(out)): 
    print i,p 

restituisce 12 coppie univoche per n = 4 e 120 per n = 6.