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

Question

我有一份足球运动员名单。每个球员都有三个属性:位置(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

Answer 1

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)