问题

我有一群人,我希望每个人与小组中的每个其他人进行1:1的 session 。一个给定的人一次只能与另一个人见面,因此我想执行以下操作:

  • 查找所有可能的配对组合
  • 组配对成“回合”的 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')}
    

    为了自己计算出回合,我正在构建一个回合,如下所示:
  • 创建一个空的round列表
  • 遍历使用
  • 上方的people_pairs方法计算出的combinations集的副本
  • 对于该对中的每个人,请检查当前round中是否存在任何已经包含该单独
  • 的配对
  • 如果已经有一对包含其中一个个体,请在本回合中跳过该配对。如果不是,请将这对添加到回合中,然后从people_pairs列表中删除该对。
  • 遍历所有人员对之后,将该回合附加到主rounds列表
  • 重新开始,因为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 :)这只是一个简单的示例,代表了我要解决的匹配/组合问题。

    最佳答案

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

    10-05 20:42
    查看更多