從2元組列表生成3元組的最大數目

Question

我有一個2元組列表，並希望從列表中生成儘可能多的3元組。例如：

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

即

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

現在我想找到可以從該列表中生成的循環3元組的最大數量，一個這樣的3元組將是：

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

每個2元組只能使用一次。我想我可以使用暴力方法，但我有一種感覺，它可以以更聰明的方式完成。有什麼想法嗎？

對於任何有興趣的人來說，這個問題是一個調度問題。 n個球隊在一個賽季中應該互相打一次球。一個賽季包括一系列比賽，理想情況下比賽由3支隊伍組成，其中3支隊伍相互對戰（總共3場比賽）。目標是避免只有兩支球隊的比賽。

Answer 1

使用itertools.permutations()來生成循環比較容易。

你的數據集有多大。對於小型數據集，你可以簡單的蠻力它itertools.product()，如：

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

所以我現在明白你的問題，你可以採取較爲積極的做法，如：

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