python - 找到最有效的对组

Question

问题

我有一群人，我希望每个人都与小组中的其他人进行 1 对 1 session 。给定的人一次只能与另一个人见面，所以我想做以下事情:

1. 找到所有可能的配对组合
2. 将配对组合成“回合” session ，其中每个人只能参加一次回合，并且回合应包含尽可能多的配对，以便在最少的回合中满足所有可能的配对组合。<

为了说明所需输入/输出方面的问题，假设我有以下列表:

>>> people = ['Dave', 'Mary', 'Susan', 'John']

我想产生以下输出:

>>> for round in make_rounds(people):
>>>     print(round)
[('Dave', 'Mary'), ('Susan', 'John')]
[('Dave', 'Susan'), ('Mary', 'John')]
[('Dave', 'John'), ('Mary', 'Susan')]

如果我的人数是奇数，那么我会期待这样的结果:

>>> people = ['Dave', 'Mary', 'Susan']
>>> for round in make_rounds(people):
>>>     print(round)
[('Dave', 'Mary')]
[('Dave', 'Susan')]
[('Mary', 'Susan')]

这个问题的关键是我需要我的解决方案是高性能的(在合理的范围内)。我已经编写了工作的代码，但是随着people的规模增长，它变得指数级地变慢。我对编写高性能算法知之甚少，无法知道我的代码是否效率低下，或者我是否只是受问题参数的约束

我尝试过的

第 1 步很简单:我可以使用 itertools.combinations 获得所有可能的配对:

>>> from itertools import combinations
>>> people_pairs = set(combinations(people, 2))
>>> print(people_pairs)
{('Dave', 'Mary'), ('Dave', 'Susan'), ('Dave', 'John'), ('Mary', 'Susan'), ('Mary', 'John'), ('Susan', 'John')}

为了自己计算回合，我正在构建一个这样的回合:

1. 创建一个空的round列表
2. 迭代使用上述 combinations 方法计算的 people_pairs 集的副本
3. 对于配对中的每个人，检查当前 round 中是否有任何现有配对已经包含该个人
4. 如果已经有一对包含其中一个人，则在本轮中跳过该配对。如果不是，则将该对添加到回合中，然后从 people_pairs 列表中删除该对。
5. 一旦所有的人对都被迭代完，将这一轮追加到一个主rounds列表
6. 重新开始，因为 people_pairs 现在只包含未进入第一轮的配对

最终，这会产生所需的结果，并减少我的人员配对，直到没有剩余并且计算所有回合。我已经可以看到这需要大量的迭代，但我不知道更好的方法。

这是我的代码:

from itertools import combinations

# test if person already exists in any pairing inside a round of pairs
def person_in_round(person, round):
    is_in_round = any(person in pair for pair in round)
    return is_in_round

def make_rounds(people):
    people_pairs = set(combinations(people, 2))
    # we will remove pairings from people_pairs whilst we build rounds, so loop as long as people_pairs is not empty
    while people_pairs:
        round = []
        # make a copy of the current state of people_pairs to iterate over safely
        for pair in set(people_pairs):
            if not person_in_round(pair[0], round) and not person_in_round(pair[1], round):
                round.append(pair)
                people_pairs.remove(pair)
        yield round

使用 https://mycurvefit.com 绘制列表大小为 100-300 的此方法的性能显示为 1000 人的列表计算轮数可能需要大约 100 分钟。有没有更有效的方法来做到这一点？

注意:我实际上并没有尝试组织 1000 人的 session :) 这只是一个简单的示例，代表了我要解决的匹配/组合问题。

Answer 1

这是 Wikipedia 文章 Round-robin tournament 中描述的算法的实现。 .

from itertools import cycle , islice, chain

def round_robin(iterable):
    items = list(iterable)
    if len(items) % 2 != 0:
        items.append(None)
    fixed = items[:1]
    cyclers = cycle(items[1:])
    rounds = len(items) - 1
    npairs = len(items) // 2
    return [
        list(zip(
            chain(fixed, islice(cyclers, npairs-1)),
            reversed(list(islice(cyclers, npairs)))
        ))
        for _ in range(rounds)
        for _ in [next(cyclers)]
    ]