Generieren aller eindeutigen Paarpermutationen

Question

Ich muss alle möglichen Paarungen generieren, aber mit der Einschränkung, dass eine bestimmte Paarung nur einmal in den Ergebnissen auftritt. So zum Beispiel:

import itertools 

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

generiert alle möglichen Zwei-paarweise Permutationen; hier ist eine kleine Teilmenge der Ausgabe:

... 
[(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)] 
... 

Wie kann ich es weiter filtern, so dass ich immer nur (8,4) sehe einmal (in all gefilterten Permutationen) und (8,5) nur einmal , und (0,1) nur einmal und (4,7) nur einmal, usw.?

Grundsätzlich möchte ich die Permutationen so, dass jede Zwei-Element-Paarung nur einmal passiert.

Ich wette, es gibt ein zusätzliches Itertool, das das lösen würde, aber ich bin nicht Experte genug, um zu wissen, was es ist.

aktualisieren: Gareth Rees ist richtig - ich gar nicht bewusst war, dass ich das Round-Robin-Problem zu lösen versuchte. Ich habe eine zusätzliche Einschränkung, nämlich dass ich Leute für Paarprogrammierungsübungen gruppiere. Wenn ich also eine ungerade Anzahl von Leuten habe, muss ich eine Dreiergruppe bilden, um eine ungerade Person für jede Übung einzubeziehen. Mein gegenwärtiges Denken ist, (1) eine gerade Zahl von Leuten zu machen, indem ich eine unsichtbare Person hinzufüge. Suchen Sie dann nach der Paarung die Person, die mit der unsichtbaren Person gepaart ist, und setzen Sie sie zufällig in eine bestehende Gruppe ein, um eine Dreiergruppe zu bilden. Ich frage mich jedoch, ob es nicht bereits einen Algorithmus oder eine Anpassung an das Round-Robin gibt, der dies besser macht.

Update 2: Theodros 'Lösung produziert genau das richtige Ergebnis ohne die unelegante Schminke, die ich oben beschrieben habe. Jeder war unglaublich hilfreich.

Answer 1

Ich möchte eine andere Implementierung von Round Robin teilen, die von dem Standard Library Nutzung der deque -Daten Struktur macht:

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

Es setzt die Objekte (hier) in die Deque. Dann rotiert es und baut aufeinanderfolgende Paare auf, die von beiden Enden zur Mitte führen. Man kann sich das so vorstellen, als würde man die Deque in der Mitte auf sich selbst zurückfalten. Um es klar:

Fall uneben Elemente:

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 

Bei noch Elemente ein zusätzlicher Schritt erforderlich ist.
(Ich habe das erste Mal verpasst, weil ich nur den unebenen Fall überprüft habe. Dies ergab einen schrecklich falschen Algorithmus ... der mir zeigt, wie wichtig es ist, Randfälle zu überprüfen, wenn ein Algorithmus implementiert wird ...)
Dieser spezielle Schritt ist dass ich vor jeder Drehung die beiden äußersten linken Elemente (die die ersten und letzten Elemente der Deque sind) vertausche - das heißt, die 0 bleibt die ganze Zeit oben links.

Fall sogar Elemente:

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 

Was ist mit dieser Version verfolgt mich ist die Menge an Code-Duplizierung, aber ich konnte nicht einen Weg zu verbessern und gleichzeitig halten sie so lesbar finden. Hier ist meine erste Implementierung, die weniger lesbar IMO ist:

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 

Update für die aktualisierte Frage zu berücksichtigen:

Um in dem ungleichen Fall für Gruppen von drei zu erlauben Sie brauchen nur round_robin_odd(d, n) zu ändern:

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

Das gibt:

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

Übergeben Sie die Liste an set, um sicherzustellen, dass jedes Tupel nur einmal existiert.

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

Aus Ihrer Beschreibung möchten Sie jedes der 2-Tupel Permutationen der range(9) die oben sollten Sie alle verschiedenen Permutationen geben, basierend auf Ihren Code. Aber das ist ziemlich ineffizient.

immer Sie weiter Ihren Code, indem Sie die folgenden vereinfachen kann:

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

Das Verfahren permutations nimmt auch eine Länge Argument, dass Sie die Länge des Tupels zurückgegeben angeben können. Sie haben also die korrekte itertool-Funktion verwendet, aber den Tupel-Längen-Parameter verpasst.

itertools.permutations documentation

Answer 3

Wie MatthieuW sagt in this answer sieht es so aus, als ob Sie versuchen, einen Zeitplan für einen round-robin tournament zu erzeugen. Dies kann leicht unter Verwendung this algorithm generiert werden, die Hauptschwierigkeit ist der Umgang mit einer ungeraden Anzahl von Teams (wenn jedes Team in einer Runde ein Freilos erhält).

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

Zum Beispiel mit neun Teams:

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