问题
我有一群人,我希望每个人与小组中的每个其他人进行1:1的 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)]
]