从2元组列表生成3元组的最大数目

我有一个2元组列表，并希望从列表中生成尽可能多的3元组。例如：从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场比赛）。目标是避免只有两支球队的比赛。

来源

2017-06-12 Lennart

你能涉及到[图中的周期]（http://www.geeksforgeeks.org/detect-cycle-undirected-graph/）？ –

我想，但是如果我们用无向图中的边来考虑这个问题，我们正在处理一个完整的图：https：//en.wikipedia.org/wiki/Complete_graph。然后，我们希望在该图中找到尽可能多的3个循环。 – Lennart

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

来源

2017-06-12 19:25:11 AChampion

谢谢，这个集合的大小很小（比如说少于20个二元组），所以暴力就可以做到。对于一个优雅算法的古董 – Lennart

每个2元组只能使用一次？ –

@ B.M，这是正确的。在输出（1,2）中出现多次，这是不允许的。输出必须进一步过滤，但它是一个开始 – Lennart

从2元组列表生成3元组的最大数目

回答

相关问题