python統計分析

Question

給定15名球員 - 2名守門員，5名後衛，5名中場球員和3名前鋒，以及每個球員都有一定的價值和得分的事實，我想計算出我擁有的最高得分球隊。每個團隊必須由1個GK組成，然後形成例如4：4：2，4：3：3等我開始與像這樣的樣本數據

玩家角色分成本

我那麼做了以下評價所有組合

閱讀每一行成列表（針對每個角色），然後使用itertools嵌套運行得到所有組合

if line[1] == "G": G.append(line[0]) 
if line[1] == "D": D.append(line[0]) 
if line[1] == "M": M.append(line[0]) 
if line[1] == "S": S.append(line[0]) 

for gk in itertools.combinations(G,1): 
    for de in itertools.combinations(D,4): 
     for mi in itertools.combinations(M,4): 
      for st in itertools.combinations(S,2): 
       teams[str(count)]= " ".join(gk)+" "+" ".join(de)+" "+" ".join(mi)+" "+" ".join(st) 
       count +=1 

已經得到了球隊，我計算出它們的分值，和團隊的成本。如果它低於閾值，我會打印它。
但是如果我現在讓這20個守門員，150個後衛，150箇中場球員和100個前鋒，我理解的是失去記憶。
我可以做些什麼來執行此分析？它是一個生成器而不是我需要的遞歸函數嗎？

非常感謝

Answer 1

您可能可以通過遞歸來解決這個問題。下面顯示了基本輪廓，但是忽略了一些細節，比如一個團隊由一定數量的特定類型的球員組成。

players=[{'name':'A','score':5,'cost':10}, 
     {'name':'B','score':10,'cost':3}, 
     {'name':'C','score':6,'cost':8}] 

def player_cost(player): 
    return player['cost'] 
def player_score(player): 
    return player['score'] 
def total_score(players): 
    return sum(player['score'] for player in players) 

def finance_team_recurse(budget, available_players): 
    affordable_players=[] 
    for player in available_players: 
     if player_cost(player)<=budget: 
      # Since we've ordered available players, the first player appended 
      # will be the one with the highest score. 
      affordable_players.append(player) 
    result=[] 
    if affordable_players: 
     candidate_player=affordable_players[0] 
     other_players=affordable_players[1:] 
     # if you include candidate_player on your team 
     team_with_candidate=finance_team_recurse(budget-player_cost(candidate_player), 
               other_players) 
     team_with_candidate.append(candidate_player) 
     score_of_team_with_candidate=total_score(team_with_candidate) 
     if score_of_team_with_candidate>total_score(other_players): 
      result=team_with_candidate 
     else: 
      # if you exclude candidate_player from your team 
      team_without_candidate=finance_team_recurse(budget, other_players) 
      score_of_team_without_candidate=total_score(team_without_candidate) 
      if score_of_team_with_candidate>score_of_team_without_candidate: 
       result=team_with_candidate 
      else: 
       result=team_without_candidate 
    return result 

def finance_team(budget, available_players): 
    tmp=available_players[:] 
    # Sort so player with highest score is first. (Greedy algorithm?) 
    tmp.sort(key=player_score, reverse=True) 
    return finance_team_recurse(budget,tmp) 

print(finance_team(20,players)) 
# [{'score': 6, 'cost': 8, 'name': 'C'}, {'score': 10, 'cost': 3, 'name': 'B'}] 

---

20 choose 1 = 20 combinations 
150 choose 4 = 20260275 combinations 
100 choose 2 = 4950 combinations 

因此，有總共在teams字典20 * 20260275 * 20260275 * 4950 = 40637395564486875000L 項目。這需要很多內存。

for gk in itertools.combinations(G,1): 
    for de in itertools.combinations(D,4): 
     for mi in itertools.combinations(M,4): 
      for st in itertools.combinations(S,2):  
       #Don't collect the results into a dict. 
       #That's what's killing you (memory-wise). 
       #Just compute the cost and 
       #Just print the result here. 

PS。 40637395564486875000L的訂單是10**19。假設你的程序可以每秒處理10**6組合，這將需要大約1.3百萬年的程序來完成...

Answer 2

功能和發電機有很大的幫助：

def make_teams(G, D, M, S): 
    """ returns all possible teams """ 
    for gk in itertools.combinations(G,1): 
     for de in itertools.combinations(D,4): 
      for mi in itertools.combinations(M,4): 
       for st in itertools.combinations(S,2): 
        yield gk, de, mi, st 

def get_cost(team): 
    return sum(member.cost for member in team) 

def good_teams(min_score=0): 
    for team in make_teams(G, D, M, S): 
     if get_cost(team) > min_score: 
      yield team 

for team in good_teams(min_score=100): 
    print team 

它仍然產生所有可能的組合，所以你現在可能會用完時間，而不是記憶。

你在做什麼好像knapsack problem的變化 - 你可以做的比嘗試所有可能的組合更好，但不是更好。

快速獲得良好解決方案的一種方法是按照每的分數排序玩家。你應該首先得到最高得分的球隊，但是不能保證你得到最好的解決方案。維基百科稱這爲「貪婪近似算法」。

def score_per_cost(player): 
    return player.score/player.cost 

def sorted_combinations(seq, n): 
    return itertools.combinations(
     sorted(seq, key=score_per_cost, reverse=True),n) 

def make_teams(G, D, M, S): 
    """ returns all possible teams """ 
    for gk in sorted_combinations(G,1): 
     for de in sorted_combinations(D,4): 
      for mi in sorted_combinations(M,4): 
       for st in sorted_combinations(S,2): 
        yield gk, de, mi, st 

def get_cost(team): 
    return sum(member.cost for member in team) 

def top_teams(n): 
    return itertools.islice(make_teams(G, D, M, S),n) 

for team in top_teams(100): 
    print team 

我會離開加入要求「每隊<門檻費」給讀者（提示：這是在make_teams一行：P）。