找到最有效的对组

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

这个问题的关键是我需要我的解决方案(在合理范围内).我已经写了代码工作,但随着规模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. 迭代people_pairs使用上述combinations方法计算的集合的副本
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人的会议:)这只是一个简单的例子,代表了我正在努力解决的匹配/组合问题.

Answer 1

这是维基百科文章Round-robin锦标赛中描述的算法的实现 .

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

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

当您需要快速查找时，哈希/字典就是最佳选择。跟踪谁在每一轮中都在 adict而不是 alist中，这样会快得多。

既然你正在学习算法，那么学习大 O 表示法会对你有所帮助，并且了解哪些数据结构擅长哪种操作也是关键。请参阅本指南： https: //wiki.python.org/moin/TimeComplexity了解 Python 内置函数的时间复杂度。您将看到检查列表中的项目的时间复杂度为 O(n)，这意味着它会随着输入的大小线性缩放。因此，由于它处于循环中，您最终会得到 O(n^2) 或更糟的结果。对于字典，查找通常是 O(1)，这意味着输入的大小并不重要。

另外，不要覆盖内置函数。我round改为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_