Generazione di tutte le permutazioni di coppie univoche

Question

Devo generare tutti i possibili accoppiamenti, ma con il vincolo che un particolare accoppiamento si verifica solo una volta nei risultati. Ad esempio:

import itertools 

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

genera tutte le possibili permutazioni bipartite; ecco un piccolo sottoinsieme di uscita:

... 
[(8, 4), (7, 6), (5, 3), (0, 2)] 
[(8, 4), (7, 6), (5, 3), (1, 0)] 
[(8, 4), (7, 6), (5, 3), (1, 2)] 
[(8, 4), (7, 6), (5, 3), (2, 0)] 
[(8, 4), (7, 6), (5, 3), (2, 1)] 
[(8, 5), (0, 1), (2, 3), (4, 6)] 
[(8, 5), (0, 1), (2, 3), (4, 7)] 
[(8, 5), (0, 1), (2, 3), (6, 4)] 
[(8, 5), (0, 1), (2, 3), (6, 7)] 
[(8, 5), (0, 1), (2, 3), (7, 4)] 
[(8, 5), (0, 1), (2, 3), (7, 6)] 
[(8, 5), (0, 1), (2, 4), (3, 6)] 
[(8, 5), (0, 1), (2, 4), (3, 7)] 
[(8, 5), (0, 1), (2, 4), (6, 3)] 
... 

Come faccio a filtrare ulteriormente in modo che io vedo sempre e solo (8,4) una volta (durante tutte le permutazioni filtrati), e (8,5) solo una volta e (0,1) solo una volta e (4,7) una sola volta, ecc.?

Fondamentalmente voglio le permutazioni in modo che ogni accoppiamento di due elementi avvenga solo una volta.

Scommetto che c'è un itertoolo aggiuntivo che risolverebbe questo problema ma non sono abbastanza esperto per sapere di cosa si tratta.

Aggiornamento: Gareth Rees è corretto - ero completamente all'oscuro del fatto che stavo cercando di risolvere il problema del round robin. Ho un ulteriore vincolo che è quello che sto facendo è raggruppare le persone per esercizi di programmazione della coppia. Quindi, se ho un numero dispari di persone, ho bisogno di creare un gruppo di tre persone per includere una persona strana per ogni esercizio. Il mio attuale pensiero è quello di (1) creare un numero pari di persone aggiungendo una persona invisibile. Quindi, dopo l'abbinamento, trova la persona accoppiata con la persona invisibile e inseriscile casualmente in un gruppo esistente per formare una squadra di tre. Tuttavia, mi chiedo se non ci sia già un algoritmo o un adeguamento al round-robin che lo faccia in un modo migliore.

Aggiornamento 2: La soluzione di Theodros produce esattamente il risultato giusto senza l'inutile futore su quanto descritto sopra. Tutti sono stati incredibilmente utili.

Answer 1

Mi piacerebbe condividere una diversa implementazione di scheduling round-robin che fa uso della struttura -data deque dalla libreria standard:

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


print round_robin(5) 
    [[[0, 4], [1, 3]], 
    [[4, 3], [0, 2]], 
    [[3, 2], [4, 1]], 
    [[2, 1], [3, 0]], 
    [[1, 0], [2, 4]]] 


print round_robin(2) 
    [[[0, 1]]] 

Mette gli oggetti (ints qui) nel deque. Quindi ruota e costruisce coppie consecutive prendendo da entrambe le estremità verso il centro. Si può immaginare questo come piegare la deque nel mezzo su se stessa. Per chiarire:

Caso elementi irregolari:

round 1  round 2  # pairs are those numbers that sit 
---------- ---------  # on top of each other 
0 1 2 3 4 8 0 1 2 3 
8 7 6 5  7 6 5 4 

In caso di anche elementi è necessario un ulteriore passaggio.
(Ho perso la prima volta perché ho controllato solo il caso non uniforme. Ciò ha prodotto un algoritmo orribilmente sbagliato ... che mi mostra quanto sia importante controllare i casi limite quando si implementa un algoritmo ...)
Questo passaggio speciale è che scambio i due elementi più a sinistra (che sono il primo e l'ultimo elemento del deque) prima di ogni rotazione - questo significa che lo 0 rimane sempre in alto a sinistra.

caso anche elementi:

round 1  round 2  # pairs are those numbers that sit 
---------- ---------  # on top of each other 
0 1 2 3  0 7 1 2 
7 6 5 4  6 5 4 3 

Ciò che mi ossessiona su questa versione è la quantità di duplicazione del codice, ma non riuscivo a trovare un modo per migliorare, mantenendo come leggibile. Ecco la mia prima implementazione, che è meno leggibile IMO:

def round_robin(n): 
    is_even = (n % 2 == 0) 
    schedule = [] 
    d = deque(range(n)) 
    for i in range(2 * ((n - 1)/2) + 1): 
     schedule.append(
         [[d[j], d[-j-1]] for j in range(n/2)]) 
     if is_even: 
      d[0], d[-1] = d[-1], d[0] 
     d.rotate() 
    return schedule 

aggiornamento per tenere conto della domanda aggiornamento:

Per consentire nel caso irregolare per gruppi di tre Hai solo bisogno di cambiare round_robin_odd(d, n):

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

Questo dà:

print round_robin(5) 
[[[0, 4], [1, 3, 2]], 
[[4, 3], [0, 2, 1]], 
[[3, 2], [4, 1, 0]], 
[[2, 1], [3, 0, 4]], 
[[1, 0], [2, 4, 3]]] 

Answer 2

Passare l'elenco a set per assicurarsi che ciascuna tupla esista solo una volta.

>>> from itertools import permutations 
>>> set([ zip(perm[::2], perm[1::2]) for perm in permutations(range(9)) ]) 
set([(7, 3), (4, 7), (1, 3), (4, 8), (5, 6), (2, 8), (8, 0), (3, 2), (2, 1), (6, 2), (1, 6), (5, 1), (3, 7), (2, 5), (8, 5), (0, 3), (5, 8), (4, 0), (1, 2), (3, 8), (3, 1), (6, 7), (2, 0), (8, 1), (7, 6), (3, 0), (6, 3), (1, 5), (7, 2), (3, 6), (0, 4), (8, 6), (3, 5), (4, 1), (6, 4), (5, 4), (2, 6), (8, 2), (2, 7), (7, 1), (4, 5), (8, 3), (1, 4), (6, 0), (7, 5), (2, 3), (0, 7), (8, 7), (4, 2), (1, 0), (0, 8), (6, 5), (4, 6), (0, 1), (5, 3), (7, 0), (6, 8), (3, 4), (6, 1), (5, 7), (5, 2), (0, 2), (7, 4), (0, 6), (1, 8), (4, 3), (1, 7), (0, 5), (5, 0), (7, 8), (2, 4), (8, 4)]) 

Dalla tua descrizione si vuole ciascuna delle permutazioni 2-tuple del range(9) cui sopra dovrebbe darvi tutte le varie permutazioni, in base al codice. Ma questo è abbastanza inefficiente.

Tuttavia è possibile semplificare ulteriormente il codice nel modo seguente:

>>> list(permutations(range(9), 2)) 
[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (1, 0), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 0), (2, 1), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (3, 0), (3, 1), (3, 2), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (4, 0), (4, 1), (4, 2), (4, 3), (4, 5), (4, 6), (4, 7), (4, 8), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4), (5, 6), (5, 7), (5, 8), (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 7), (6, 8), (7, 0), (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 6), (7, 8), (8, 0), (8, 1), (8, 2), (8, 3), (8, 4), (8, 5), (8, 6), (8, 7)] 

Il metodo permutations prende anche un argomento di lunghezza che vi permetterà di specificare la lunghezza della tupla restituita. Quindi, stavi usando la corretta funzione itertool, ma mancava il parametro della lunghezza della tupla.

itertools.permutations documentation

Answer 3

Come MatthieuW dice in this answer, sembra come se si sta cercando di generare una pianificazione per un round-robin tournament. Questo può essere facilmente generato usando this algorithm, la difficoltà principale è la gestione di un numero dispari di squadre (quando ogni squadra ottiene un ciao in un round).

def round_robin_schedule(n): 
    """ 
    Generate a round-robin tournament schedule for `n` teams. 
    """ 
    m = n + n % 2    # Round up to even number. 
    for r in xrange(m - 1): 
     def pairing(): 
      if r < n - 1: 
       yield r, n - 1 
      for i in xrange(m // 2 - 1): 
       p, q = (r + i + 1) % (m - 1), (m + r - i - 2) % (m - 1) 
       if p < n - 1 and q < n - 1: 
        yield p, q 
     yield list(pairing()) 

Per esempio, con nove squadre:

>>> list(round_robin_schedule(9)) 
[[(0, 8), (2, 7), (3, 6), (4, 5)], 
[(1, 8), (2, 0), (4, 7), (5, 6)], 
[(2, 8), (3, 1), (4, 0), (6, 7)], 
[(3, 8), (4, 2), (5, 1), (6, 0)], 
[(4, 8), (5, 3), (6, 2), (7, 1)], 
[(5, 8), (6, 4), (7, 3), (0, 1)], 
[(6, 8), (7, 5), (0, 3), (1, 2)], 
[(7, 8), (0, 5), (1, 4), (2, 3)], 
[(0, 7), (1, 6), (2, 5), (3, 4)]]