找到最有效的配对组

Question

我有一个团队，我希望每个人都能与团队中的其他人进行1:1的会谈。一个给定的人一次只能与另一个人见面，因此我想执行以下操作：

1. 找到所有可能的配对组合
2. 将配对分组为“轮”会议，每个人只能参加一轮会议，一轮会议应包含尽可能多的配对，以在最少的轮数中满足所有可能的配对组合

为了从期望的输入/输出方面演示问题，假设我有以下列表：

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

这个问题的关键是，我需要我的解决方案是合理的。我已经编写了一些有效的代码，但是随着人规模的增长，它的速度会呈指数级增长。我对编写性能算法了解不够，不知道我的代码是否效率低下，或者我是否仅仅受到问题参数的约束

步骤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. 创建一个空的轮列表
2. 迭代使用上述组合方法计算的人对集合的副本
3. 对于配对中的每个人，检查当前轮中是否存在已包含该个人的现有配对
4. 如果已经有一对包含其中一个个体，则跳过此轮的配对。如果没有，则将配对添加到轮次中，并将配对从人员配对列表中删除
5. 迭代所有人员对后，将轮添加到主roundslist
6. 重新开始，因为人对现在只包含没有进入第一轮的人对

最终，这会产生期望的结果，并缩减我的人员对，直到没有剩余人员，所有轮次都计算出来。我已经看到这需要大量的迭代，但我不知道更好的方法。

这是我的密码：

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
    html" target="_blank">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

在列表大小为100-300的情况下，使用https://mycurvefit.com显示为1000人计算轮次可能需要大约100分钟。有没有更有效的方法？

注意：我实际上并不是在组织一个1000人的会议：）这只是一个简单的例子，代表了我试图解决的匹配/组合问题。

Answer 1

当您需要快速查找时，哈希/迪克斯是最好的选择。跟踪谁在每个回合中的法规，而不是列表，这样会快得多。

由于您正在学习算法，学习大O表示法将帮助您解决问题，了解哪些数据结构擅长于哪种操作也是关键。请参阅本指南：https://wiki.python.org/moin/TimeComplexity对于Python内置的时间复杂性。您将看到，检查列表中的项目是O（n），这意味着它与输入的大小成线性比例。因此，因为它是在一个循环中，所以最终得到O（n^2）或更糟的结果。对于dicts，查找通常是O（1），这意味着它与输入的大小无关。

此外，不要覆盖内置。我把轮改为round_

from itertools import combinations

# test if person already exists in any pairing inside a round of pairs
def person_in_round(person, people_dict):
    return people_dict.get(person, False)

def make_rounds(people):
    people_pairs = set(combinations(people, 2))
    people_in_round = {}
    # 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_ = []
        people_dict = {}
        # 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], people_dict) and not person_in_round(pair[1], people_dict):
                round_.append(pair)
                people_dict[pair[0]] = True
                people_dict[pair[1]] = True


                people_pairs.remove(pair)
        yield round_

Answer 2

我只生成索引（因为我很难找到1000个名称=），但对于1000个数字，运行时间大约为4秒。

所有其他方法的主要问题是——它们使用对并使用对，有很多对，而且运行时间越来越长。我的方法不同于与人合作，而不是与人结对。我有一个dict（），它将此人映射到他必须会见的其他人的列表，这些列表最多有N个项目（而不是N^2，如成对）。因此节省了时间。

#!/usr/bin/env python

from itertools import combinations
from collections import defaultdict

pairs = combinations( range(6), 2 )

pdict = defaultdict(list)
for p in pairs :
    pdict[p[0]].append( p[1] )

while len(pdict) :
    busy = set()
    print '-----'
    for p0 in pdict :
        if p0 in busy : continue

        for p1 in pdict[p0] :
            if p1 in busy : continue

            pdict[p0].remove( p1 )
            busy.add(p0)
            busy.add(p1)
            print (p0, p1)

            break

    # remove empty entries
    pdict = { k : v for k,v in pdict.items() if len(v) > 0 }

'''
output:
-----
(0, 1)
(2, 3)
(4, 5)
-----
(0, 2)
(1, 3)
-----
(0, 3)
(1, 2)
-----
(0, 4)
(1, 5)
-----
(0, 5)
(1, 4)
-----
(2, 4)
(3, 5)
-----
(2, 5)
(3, 4)
'''

Answer 3

这是Wikipedia文章循环锦标赛中描述的算法的实现。

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