时间戳

首页 > 解决方案 > 如何在 Python 中创建带有约束的组合

python - 如何在 Python 中创建带有约束的组合

问题描述

我有一份足球运动员名单。每个球员都有三个属性：位置（G、D、M、A）、姓名和薪水。

Position Name     Salary
P        Buffon    6
D        Maldini  23
D        Baresi   15
D        Bergomi   7
C        Kakà     33
C        Gomez    18
A        Ronaldo  52
A        Vieri    44
...

我想创建一个包含 11 名球员的足球队的所有可能组合。这些是约束：

  1. 玩家约束：总元素 = 11
  2. 位置约束：P = 1, D = 4, C = 4, A = 2
  3. 工资限制：总工资 < 200

我已经开始研究，在我看来，itertools 可以帮助我在给定约束的情况下生成所有可能的团队。但我不清楚的是如何对约束进行编码。

subset = df[['position', 'name', 'salary']]
tuples = [tuple(x) for x in subset.values]
all_permutations = itertools.permutations(tuples)
for perm in all_permutations:
    # constrains

标签： pythoncombinationspermutationitertools

解决方案

itertools 库有一个非常好的函数用于迭代组合。您可以获得 11 个玩家的所有组合，然后通过这些组合进行过滤。

from collections import Counter
import itertools

def valid_team(team):
    positions = []
    salary = 0
    for player in team:
        (player_pos,_,player_salary)=player
        positions.append(player_pos)
        salary += player_salary
    pos_count = Counter(positions)
    return (
        pos_count['P'] is 1 and
        pos_count['D'] is 4 and
        pos_count['C'] is 4 and
        pos_count['A'] is 2 and
        salary<200
    )

for team in itertools.combinations(players,11):
    if (valid_team(team)):
        print("found valid team")
        print(team)
    else:
        print("found invalid team")

需要注意的是，上述方法中有很多不必要的处理，因为您可以单独选择每个位置。下面的替代实现。

players_sorted = {}
for player in players:
    if player[0] not in players_sorted:
        players_sorted[player[0]] = []
    players_sorted[player[0]].append(player)

p_guys = itertools.combinations(players_sorted['P'],1)
d_guys = itertools.combinations(players_sorted['D'],4)
c_guys = itertools.combinations(players_sorted['C'],4)
a_guys = itertools.combinations(players_sorted['A'],2)

teams = itertools.product(p_guys,d_guys,c_guys,a_guys)

for team in teams:
    team_players = []
    for pos in team:
        team_players.extend(pos)
    if (valid_team(team_players)):
        print("found valid team")
        print(team)
    else:
        print("found invalid team")
        print(team)

推荐阅读