从偏好列表中找到可行的组合

Question

我有一个看起来像这样的对象:

a - ['A', 'B', 'C']
b - ['A', 'B', 'C']
c - ['A', 'B', 'C', 'D']
d - ['A', 'B', 'C', 'D']

每个键具有许多可用选项,如列表所示(例如,a可以在之间进行选择A, B, C等).我想找到一对能满足每个人的组合.这可能是:

#   Chosen  Remaining          Available Options
------------------------------------------
a - B       - ['A', 'B', 'C'] - ['A', 'B', 'C']
b - A       - ['A', 'C']      - ['A', 'B', 'C']
c - D       - ['C', 'D']      - ['A', 'B', 'C', 'D']
d - C       - ['C']           - ['A', 'B', 'C', 'D']

因此,在上面的示例中a选择了item B,减少了剩余参与者的可用选项池.b然后选择项目A,依此类推.

我通过循环遍历所有参与者,根据他们可用选择池的大小来实现这一点,我的想法是,如果我的参与者只需要一个项目,那么除了给他那个项目,从中删除它之外别无选择游泳池.

import random

team_choices = {'a': ['A', 'B', 'C'],
                'b': ['A', 'B', 'C'],
                'c': ['A', 'B', 'C', 'D'],
                'd': ['A', 'B', 'C', 'D']}
teams_already_created = []
for team_b in sorted(team_choices, key=team_choices.__getitem__, reverse=False):
    available_opponents = [opponent for opponent in team_choices[team_b] if opponent not in teams_already_created]
    chosen_opponent = random.choice(available_opponents)
    teams_already_created.append(chosen_opponent)

我这样做的方式并不总能很好地发挥作用,因为无法保证在某些时候它会做出选择,以后会吸引其他玩家,让他没有可用的选择.如果chosen_opponent是空的那么显然这会失败.

有没有更好的方法来做到这一点,每次都有效？

Answer 1

这就是寻找最大匹配的问题。有多项式时间算法（例如，Hopcroft\xe2\x80\x93Karp）。

\n