Erzeugen einer maximalen Anzahl von 3-Tupeln aus einer Liste von 2-Tupeln

Question

Ich habe eine Liste von 2-Tupeln und möchte so viele 3-Tupel wie möglich aus dieser Liste erzeugen. Beispiel:

#!/usr/bin/python 
import itertools 
a = list(itertools.combinations([1,2,3,4,5,6,7,8,9], 2)) 

dh

a = [(1, 2), (1, 3), ..., (1, 9), (2, 3), ..., (8, 9)] 

Nun würde Ich mag die maximale Menge an zyklischen 3-Tupel finden, die aus dieser Liste erzeugt werden kann, würde ein solches 3-Tupel sein:

(1,2),(2,3),(1,3) -> (1,2,3) 

Jedes 2-Tupel kann nur einmal verwendet werden. Ich nehme an, ich könnte einen Brute-Force-Ansatz verwenden, aber ich habe das Gefühl, dass es viel klüger gemacht werden kann. Irgendwelche Gedanken?

Für alle Interessierten ist das Problem ein Zeitplanproblem. n Teams sollten während einer Saison einmal gegeneinander spielen. Eine Saison besteht aus einer Reihe von Turnieren, idealerweise besteht ein Turnier aus 3 Teams, in denen alle 3 Teams gegeneinander spielen (insgesamt 3 Spiele in einem solchen Turnier). Ziel ist es, Turniere mit nur zwei Mannschaften zu vermeiden.

Answer 1

Es ist einfacher, itertools.permutations() zu verwenden, um Zyklen zu generieren.

Wie groß ist Ihr Datensatz? Für kleine Datensätze können Sie einfach Brute-Force mit itertools.product(), zB:

In [1]: 
import itertools as it 

a = list(it.permutations([1,2,3,4,5,6,7,8,9], 2)) 
cycle = lambda x, y, z: x[1] == y[0] and y[1] == z[0] and z[1] == x[0] 
[(x, y, z) for x, y, z in it.product(a, repeat=3) if cycle(x, y, z)] 

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

So, jetzt verstehe ich dein Problem, können Sie einen konstruktiveren Ansatz, zum Beispiel:

In [2]: 
from collections import deque 

a = [1,2,3,4,5,6,7,8,9]  
sched = [[x for x in zip(*[iter(a)]*3)]] 
for i in range(3): 
    r = [] 
    for i, x in enumerate(sched[-1]): 
     x = deque(x) 
     x.rotate(i) 
     r.append(x) 
    sched.append(list(zip(*r))) 
sched 

Out[2]: 
[[(1, 2, 3), (4, 5, 6), (7, 8, 9)], 
[(1, 6, 8), (2, 4, 9), (3, 5, 7)], 
[(1, 9, 5), (6, 2, 7), (8, 4, 3)], 
[(1, 7, 4), (9, 6, 3), (5, 2, 8)]]