Python熊貓自我加入合併笛卡爾積產生所有組合和總和

Question

我是Python的新手，看起來像它有很多靈活性並且比傳統的RDBMS系統更快。

創建一個非常簡單的過程來創建隨機幻想團隊。我來自RDBMS背景（Oracle SQL），對於這種數據處理來說這似乎不是最佳的。

我做了使用熊貓從CSV文件中讀取一個數據幀，現在有兩列的簡單數據框 - 球員，薪資：

`     Name Salary 
0    Jason Day 11700 
1   Dustin Johnson 11600 
2   Rory McIlroy 11400 
3   Jordan Spieth 11100 
4   Henrik Stenson 10500 
5   Phil Mickelson 10200 
6   Justin Rose 9800 
7    Adam Scott 9600 
8   Sergio Garcia 9400 
9   Rickie Fowler 9200` 

我試圖通過Python做（熊貓）是所有生產6個球員的組合，其工資是一定的數額45000 - 50000.

在查找python選項，我發現itertools組合有趣，但它會導致大量列表的組合，而不會過濾薪水的總和。

在傳統的SQL，我會做一個大規模的合併笛卡爾加入W/SUM，但後來我獲得了玩家在不同地點..

如A，B，C，那麼，C，B，A。 。

我不足夠好工作，傳統的SQL是這樣的：

` SELECT distinct 
ONE.name AS "1", 
    TWO.name AS "2", 
    THREE.name AS "3", 
     FOUR.name AS "4", 
    FIVE.name AS "5", 
    SIX.name AS "6", 
    sum(one.salary + two.salary + three.salary + four.salary + five.salary + six.salary) as salary 
    FROM 
    nl.pgachamp2 ONE,nl.pgachamp2 TWO,nl.pgachamp2 THREE, nl.pgachamp2 FOUR,nl.pgachamp2 FIVE,nl.pgachamp2 SIX 
where ONE.name != TWO.name 
and ONE.name != THREE.name 
and one.name != four.name 
and one.name != five.name 
and TWO.name != THREE.name 
and TWO.name != four.name 
and two.name != five.name 
and TWO.name != six.name 
and THREE.name != four.name 
and THREE.name != five.name 
and three.name != six.name 
and five.name != six.name 
and four.name != six.name 
and four.name != five.name 
and one.name != six.name 
group by ONE.name, TWO.name, THREE.name, FOUR.name, FIVE.name, SIX.name` 

有沒有辦法在熊貓/ Python來做到這一點？

任何可以指向的文檔都會很棒！

Answer 1

下面是使用一個簡單的算法爲非熊貓的解決方案。它從按薪水排序的玩家列表中遞歸地生成組合。這可以讓它跳過生成超過工資上限的組合。

正如piRSquared提到的那樣，沒有6個團隊落在問題中所述的薪金範圍內，所以我選擇了限制來產生少量團隊。

#!/usr/bin/env python3 

''' Limited combinations 

    Generate combinations of players whose combined salaries fall within given limits 

    See http://stackoverflow.com/q/38636460/4014959 

    Written by PM 2Ring 2016.07.28 
''' 

data = '''\ 
0    Jason Day 11700 
1   Dustin Johnson 11600 
2   Rory McIlroy 11400 
3   Jordan Spieth 11100 
4   Henrik Stenson 10500 
5   Phil Mickelson 10200 
6   Justin Rose 9800 
7    Adam Scott 9600 
8   Sergio Garcia 9400 
9   Rickie Fowler 9200 
''' 

data = [s.split() for s in data.splitlines()] 
all_players = [(' '.join(u[1:-1]), int(u[-1])) for u in data] 
all_players.sort(key=lambda t: t[1]) 
for i, row in enumerate(all_players): 
    print(i, row) 
print('- '*40) 

def choose_teams(free, num, team=(), value=0): 
    num -= 1 
    for i, p in enumerate(free): 
     salary = all_players[p][1] 
     newvalue = value + salary 
     if newvalue <= hi: 
      newteam = team + (p,) 
      if num == 0: 
       if newvalue >= lo: 
        yield newteam, newvalue 
      else: 
       yield from choose_teams(free[i+1:], num, newteam, newvalue) 
     else: 
      break 

#Salary limits 
lo, hi = 55000, 60500 

#Indices of players that can be chosen for a team 
free = tuple(range(len(all_players))) 

for i, (t, s) in enumerate(choose_teams(free, 6), 1): 
    team = [all_players[p] for p in t] 
    names, sals = zip(*team) 
    assert sum(sals) == s 
    print(i, t, names, s) 

輸出

0 ('Rickie Fowler', 9200) 
1 ('Sergio Garcia', 9400) 
2 ('Adam Scott', 9600) 
3 ('Justin Rose', 9800) 
4 ('Phil Mickelson', 10200) 
5 ('Henrik Stenson', 10500) 
6 ('Jordan Spieth', 11100) 
7 ('Rory McIlroy', 11400) 
8 ('Dustin Johnson', 11600) 
9 ('Jason Day', 11700) 
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
1 (0, 1, 2, 3, 4, 5) ('Rickie Fowler', 'Sergio Garcia', 'Adam Scott', 'Justin Rose', 'Phil Mickelson', 'Henrik Stenson') 58700 
2 (0, 1, 2, 3, 4, 6) ('Rickie Fowler', 'Sergio Garcia', 'Adam Scott', 'Justin Rose', 'Phil Mickelson', 'Jordan Spieth') 59300 
3 (0, 1, 2, 3, 4, 7) ('Rickie Fowler', 'Sergio Garcia', 'Adam Scott', 'Justin Rose', 'Phil Mickelson', 'Rory McIlroy') 59600 
4 (0, 1, 2, 3, 4, 8) ('Rickie Fowler', 'Sergio Garcia', 'Adam Scott', 'Justin Rose', 'Phil Mickelson', 'Dustin Johnson') 59800 
5 (0, 1, 2, 3, 4, 9) ('Rickie Fowler', 'Sergio Garcia', 'Adam Scott', 'Justin Rose', 'Phil Mickelson', 'Jason Day') 59900 
6 (0, 1, 2, 3, 5, 6) ('Rickie Fowler', 'Sergio Garcia', 'Adam Scott', 'Justin Rose', 'Henrik Stenson', 'Jordan Spieth') 59600 
7 (0, 1, 2, 3, 5, 7) ('Rickie Fowler', 'Sergio Garcia', 'Adam Scott', 'Justin Rose', 'Henrik Stenson', 'Rory McIlroy') 59900 
8 (0, 1, 2, 3, 5, 8) ('Rickie Fowler', 'Sergio Garcia', 'Adam Scott', 'Justin Rose', 'Henrik Stenson', 'Dustin Johnson') 60100 
9 (0, 1, 2, 3, 5, 9) ('Rickie Fowler', 'Sergio Garcia', 'Adam Scott', 'Justin Rose', 'Henrik Stenson', 'Jason Day') 60200 
10 (0, 1, 2, 3, 6, 7) ('Rickie Fowler', 'Sergio Garcia', 'Adam Scott', 'Justin Rose', 'Jordan Spieth', 'Rory McIlroy') 60500 
11 (0, 1, 2, 4, 5, 6) ('Rickie Fowler', 'Sergio Garcia', 'Adam Scott', 'Phil Mickelson', 'Henrik Stenson', 'Jordan Spieth') 60000 
12 (0, 1, 2, 4, 5, 7) ('Rickie Fowler', 'Sergio Garcia', 'Adam Scott', 'Phil Mickelson', 'Henrik Stenson', 'Rory McIlroy') 60300 
13 (0, 1, 2, 4, 5, 8) ('Rickie Fowler', 'Sergio Garcia', 'Adam Scott', 'Phil Mickelson', 'Henrik Stenson', 'Dustin Johnson') 60500 
14 (0, 1, 3, 4, 5, 6) ('Rickie Fowler', 'Sergio Garcia', 'Justin Rose', 'Phil Mickelson', 'Henrik Stenson', 'Jordan Spieth') 60200 
15 (0, 1, 3, 4, 5, 7) ('Rickie Fowler', 'Sergio Garcia', 'Justin Rose', 'Phil Mickelson', 'Henrik Stenson', 'Rory McIlroy') 60500 
16 (0, 2, 3, 4, 5, 6) ('Rickie Fowler', 'Adam Scott', 'Justin Rose', 'Phil Mickelson', 'Henrik Stenson', 'Jordan Spieth') 60400 

---

如果你正在使用Python的舊版本不支持yield from語法，你可以用

替代

yield from choose_teams(free[i+1:], num, newteam, newvalue) 

for t, v in choose_teams(free[i+1:], num, newteam, newvalue): 
    yield t, v 

Answer 2

我跑了這6個組合，發現沒有團隊滿意。我用5代替。

這應該讓你有：

from itertools import combinations 
import pandas as pd 


s = df.set_index('Name').squeeze() 
combos = pd.DataFrame([c for c in combinations(s.index, 5)]) 
combo_salary = combos.apply(lambda x: s.ix[x].sum(), axis=1) 
combos[(combo_salary >= 45000) & (combo_salary <= 50000)] 

Answer 3

正如評論中所述，這是一個約束滿足問題。它有一個組合部分，但由於您沒有定義最小化或最大化的目標，所以它不是最優化問題（還）。你可以用很多方式來解決這個問題：你可以嘗試像piRSquared這樣的暴力破解，或者使用像PM 2Ring這樣的啓發式算法。我將用0-1線性規劃提出解決方案，並使用PuLP庫來建模和解決問題。

from pulp import * 
import pandas as pd 
df = df.set_index('Name') 
feasible_solutions = [] 

爲了模擬這個問題，首先需要定義決策變量。在這裏，決策變量將是每個玩家的指標變量：如果該玩家被選中，則該變量爲1，否則爲0。這裏是你如何在紙漿做到這一點：

players = LpVariable.dicts('player', df.index.tolist(), 0, 1, LpInteger) 

接下來，創建了一個問題：

prob = pulp.LpProblem('Team Selection', pulp.LpMinimize) 

正如我前面提到的，你的問題沒有說明任何目標。你只想創建所有可能的團隊。因此，我們將定義一個任意的目標函數（我會再次回到這個任意函數）。

prob += 0 

您主要有兩個限制：

1）該小組將有5名球員：

請記住，玩家字典中存儲我們的決策變量。 players[player]是1（如果該玩家在隊中）或0（否則）。因此，如果將所有數字相加，結果應該等於5.

2）總薪水應該在45k到50k之間。

prob += lpSum([players[player] * df.at[player, 'Salary'] 
             for player in players]) <= 50000 
prob += lpSum([players[player] * df.at[player, 'Salary'] 
             for player in players]) >= 45000 

這與第一個約束類似。在這裏，我們不計算，而是總計工資（當隊員在隊伍中時，值爲1，因此它將乘以相應的工資），否則該值將爲零，並且乘法也將爲零） 。

主要建模在這裏完成。如果您撥打prob.solve()，它會發現滿足這些限制條件的解決方案a。通常，在優化問題中，我們提供了一個目標函數，並試圖將其最大化或最小化。例如，假設你有玩家技能的分數。你的預算是有限的，你不能繼續選擇前5名球員。因此，在我們陳述prob += 0的部分，您可以定義一個目標函數來最大化總技能分數。但那不是你想要的，所以讓我們繼續。

一旦找到解決方案，您可以添加另一個約束，指出下一個解決方案應該與此不同，您可以生成所有解決方案。

while prob.solve() == 1: 
    current_solution = [player for player in players if value(players[player])] 
    feasible_solutions.append(current_solution) 
    prob += lpSum([players[player] for player in current_solution]) <= 4 

prob.solve()是解決問題的方法。根據結果​​，它返回一個整數。如果找到最優解，則結果爲1.對於不可行解或無界解，存在不同的代碼。所以只要我們能找到新的解決方案，我們就繼續循環。

在循環中，我們首先將當前解決方案附加到我們的feasible_solutions列表中。然後，我們增加另一個約束：對於這5個玩家，變量的總和不能超過4（最大值5，如果它是5，我們知道這是相同的解決方案）。

如果你運行這個，你將會得到與piRSquared相同的結果。

那麼，什麼是這樣做的好處？

我們使用整數/二進制線性編程的主要原因是組合數量增長非常快。這叫做combinatorial explosion。看看可能的團隊數量（沒有任何限制）：

from scipy.misc import comb 
comb(10, 5) 
Out: 252.0 

comb(20, 5) 
Out: 15504.0 

comb(50, 5) 
Out: 2118760.0 

comb(100, 5) 
Out: 75287520.0 

幾乎不可能評估所有組合。

當然，如果您想列出滿足這些限制條件的所有組合，您仍然存在這種風險。如果滿足約束條件的組合數量很大，則需要花費大量的時間進行計算。你無法避免這種情況。但是，如果該子集很小或者它仍然很大，但是您正在評估該集合上的函數，則會好很多。

例如，考慮下面的數據幀：

import numpy as np 
np.random.seed(0) 
df = pd.DataFrame({'Name': ['player' + str(i).zfill(3) for i in range(100)], 
        'Salary': np.random.randint(0, 9600, 100)}) 

268 75287520的解決方案滿足薪水條件。我的電腦花了44秒鐘列出它們。需要花費數小時才能使用暴力（更新：需要8小時21分鐘）。

默認情況下，PuLP使用開源求解器Cbc。還有其他可以與PuLP一起使用的開源/商業替代解算器。商業用戶的預期速度通常更快（但它們非常昂貴）。

另一種選擇是約束編程，正如我在評論中提到的那樣。對於這些問題，您可以找到許多巧妙的方法來通過約束編程來減少搜索空間。我對整型編程感到滿意，所以我展示了一個基於此的模型，但我應該注意，約束編程可能會更好。