查找最有效的对

Question

问题

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

查找所有可能的配对组合

将配对成组进行“回合”会议，每个人只能参加一次回合，并且回合应包含尽可能多的对，以满足最少回合中所有可能的配对组合。

为了用所需的输入/输出来演示该问题，假设我有以下列表：

>>> 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现在只包含未进入第一轮的对

最终，这产生了预期的结果，并减少了我的员工对，直到没有人剩下，并计算了所有回合。我已经知道这需要大量的迭代，但是我不知道这样做的更好方法。

使用https://mycurvefit.com绘制100-300列表大小的方法的性能表明，计算1000人的列表轮数可能需要100分钟左右。有更有效的方法吗？

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

Answer 1

from itertools import cycle , islice, chaindef 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 pythonfrom itertools import combinationsfrom collections import defaultdictpairs = 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

您可以立即做两件事：不要每次都通过列表复制该集合。那是浪费大量的时间/内存。而是在每次迭代后修改一次集。在每个回合中保留一组单独的人。在一个集合中查找一个人比在整个回合中循环要快一个数量级。前任：def make_rounds(people):    people_pairs = set(combinations(people, 2))    while people_pairs:        round = set()        people_covered = set()        for pair in people_pairs:            if pair[0] not in people_covered \               and pair[1] not in people_covered:                round.add(pair)                people_covered.update(pair)        people_pairs -= round # remove thi        yield round比较：