查找最有效的对

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, 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

您可以立即做两件事：

不要每次都通过列表复制该集合。那是浪费大量的时间/内存。而是在每次迭代后修改一次集。

在每个回合中保留一组单独的人。在一个集合中查找一个人比在整个回合中循环要快一个数量级。

前任：

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

比较：