时间戳

首页 > 解决方案 > 从偏好列表中找到可行的组合

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

问题描述

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

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是空的，那么显然这将失败。

有没有更好的方法可以每次都有效？

标签： pythonpython-3.xalgorithmsortingpermutation

解决方案

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

推荐阅读