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

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 选择了项目 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

这是找一个maximum matching的问题.有多项式时间算法(例如 Hopcroft–Karp )。