python – 从首选项列表中查找可行组合

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python – 从首选项列表中查找可行组合，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1473字，纯文字阅读大概需要3分钟。

内容图文

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

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

每个密钥具有多个可用选项,如列表所示(例如,可以在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']

因此,在上面的示例中,选择了项目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)

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

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

解决方法:

这是找到maximum matching的问题.存在多项式时间算法(例如,Hopcroft–Karp).

内容总结

以上是互联网集市为您收集整理的python – 从首选项列表中查找可行组合全部内容，希望文章能够帮你解决python – 从首选项列表中查找可行组合所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端