Python: Alle Pairwise-Unique Pairings erzeugen

Question

Ich suche nach einer Pythonic-Methode, um alle paarweise eindeutige eindeutige Paarungen (wo eine Paarung ist ein System, bestehend aus Paaren, und paarweise-eindeutige bedeutet, dass (a,b) ≠ (b,a)) für ein Set mit geraden Nummer n Artikel.

Ich mag den Code aus here:

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

außer dass es erzeugt alle auftrags einzigartig, paarweise einzigartige Paarungen oder (n/2)! mal mehr Paarungen als ich (Redundanz) wollen, die, obwohl ich filtern out, wirklich mein Programm im großen Maßstab n.

Das heißt, für n = 4, ich bin auf der Suche nach der folgenden Ausgabe (12 einzigartige Paarungen):

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

Beachten Sie, dass (a,b) ≠ (b,a).

Ist das möglich? Ich bin auch in Ordnung mit einer Funktion, die die 3 nicht paarweisen eindeutigen Paarungen für n = 4 erzeugt, wo (a,b) = (b,a), wie es ist einfach zu vervielfachen, was ich brauche von dort. Mein Hauptziel ist es, die überflüssigen Permutationen in der Reihenfolge der Paare in der Paarung zu vermeiden.

Vielen Dank im Voraus für Ihre Hilfe und Vorschläge-ich schätze es wirklich.

Answer 1

Ich denke, das gibt Ihnen die grundlegenden Paarungen, die Sie benötigen: 1 wenn N=2; 3 wenn N=4; 15 wenn N=6; 105 wenn n=8 usw.

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

in der verknüpften Frage „alle eindeutigen Paar Permutationen Generieren“, (here) wird ein Algorithmus einer Round-Robin-Zeitplans für jede gegebene n erzeugen gegeben. Das heißt, jeder mögliche Satz von Paarungen/Kombinationen für n Teams.

Also für n = 4 (unter der Annahme, exklusiv), das wäre:

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

Jetzt haben wir jede dieser Partitionen erhalten, wir müssen nur ihre Permutationen finden, um die vollständige Liste zu erhalten von Paarungen. dh [0, 3], [1, 2] ist ein Mitglied einer Gruppe von vier: [0, 3], [1, 2] (selbst) und [3, 0], [1, 2] und [0, 3], [2, 1] und [3, 0], [2, 1].

Um alle Mitglieder einer Gruppe von einem Mitglied zu erhalten, nehmen Sie die Permutation, bei der jedes Paar entweder umgedreht oder nicht umgedreht werden kann (wenn es zB n-Tupel statt Paare wären, dann gäbe es n ! Optionen für jeden). Da Sie also zwei Paare und Optionen haben, ergibt jede Partition 2^2 Paarungen. Du hast also insgesamt 12.

Code, um dies zu tun, wobei round_robin (n) eine Liste von Listen von Paaren zurückgibt. Also 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) 

Diese Methode erzeugt weniger als Sie wollen und dann nach oben geht, anstatt mehr zu erzeugen, als Sie wollen und immer von einem Bündel befreien, so sollte es effizienter sein. ([:: - 1] ist Voodoo, um eine Liste unwiderruflich umzukehren).

Und hier ist der Round-Robin-Algorithmus von der anderen Posting (geschrieben von 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

Ich bin nicht sicher, ob ich das Problem gut verstanden, jedenfalls hier ist meine Lösung:

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 

es gibt 12 eindeutige Paare für n = 4 und 120 für n = 6 zurück.