从首选项列表中找到可行的组合

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然后选择item 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–Karp）。