python - 从组合列表中选择对的最佳策略

Question

问题:有人可以帮我弄清楚如何计算具有最大对数的循环(每个循环三个 - 参见最后一个示例)吗？

这就是我想要做的:
-> 每个周期将两个用户配对，这样
- 每个用户在给定周期内仅与其他用户配对一次
- 在所有周期中，每个用户只与其他每个用户配对一次

现实世界:
您每周都会从列表中认识一个新人(周 = 周期)。
你再也见不到同一个人了。
每个用户每周都会与其他人匹配

这是我的问题:
我能够创建用户组合并选择从未见过面的用户对。但是，有时我只能在一个循环中匹配两对而不是三对。所以，我正在寻找一种方法来从组合列表中创建最佳选择。

1) 我从 6 个用户开始:

users = ["A","B","C","D","E","F"]

2) 从这个列表中，我创建了可能的组合:

 x = itertools.combinations(users,2)
    for i in x:
        candidates.append(i)

这给了我:

 .   A,B  A,C  A,D A,E A,F
 .    .   B,C  B,D B,E B,F
 .    .    .   C,D C,E C,F
 .    .    .    .  D,E D,F
 .    .    .    .   .  E,F

或

   candidates = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('A', 'E'), ('A', 'F'), ('B', 'C'), 
       ('B', 'D'), ('B', 'E'), ('B', 'F'), ('C', 'D'), ('C', 'E'), ('C', 'F'), 
       ('D', 'E'), ('D', 'F'), ('E', 'F')]

3) 现在，我想从这个列表中选择配对，这样一个用户(A 到 F)只出现一次并且所有用户都与这个周期中的某个人配对

例子:

cycle1 = ('A','B'),('C','D') ('E','F')

下一个循环，我想找到另一组三对。

我计算出如果有 6 个用户，应该有 5 个周期，每个周期有 3 对:

例子:

cycle 1: AF BC DE
cycle 2: AB CD EF
cycle 3: AC BE DF
cycle 4: AE BD CF
cycle 5: AD BF CE

谁能帮我弄清楚如何计算具有最大对数的循环(每个循环三个 - 参见最后一个示例)？

Answer 1

就像评论中提到的 Whatang 一样，您的问题实际上等同于创建一个 round-robin style tournament 的问题。 .这是维基百科页面上提到的算法的 Python 版本，另请参阅 this和 this answer.

def schedule(users):
    # first make copy or convert to list with length `n`
    users = list(users)  
    n = len(users)

    # add dummy for uneven number of participants
    if n % 2:  
        users.append('_')
        n += 1

    cycles = []
    for _ in range(n-1):
        # "folding", `//` for integer division
        c = zip(users[:n//2], reversed(users[n//2:]))
        cycles.append(list(c))

        # rotate, fixing user 0 in place
        users.insert(1, users.pop())
    return cycles

schedule(['A', 'B', 'C', 'D', 'E', 'F'])

对于您的示例，它会生成以下内容:

[[('A', 'F'), ('B', 'E'), ('C', 'D')],
 [('A', 'E'), ('F', 'D'), ('B', 'C')],
 [('A', 'D'), ('E', 'C'), ('F', 'B')],
 [('A', 'C'), ('D', 'B'), ('E', 'F')],
 [('A', 'B'), ('C', 'F'), ('D', 'E')]]