如何防止36K X 36K X 36K的排列來計算

Question

我有一個很好的規劃工作，我只是不能左右我的頭（除了蠻力，這是太大處理）。我們正在組織12人的高爾夫之旅。我們打4天的高爾夫球。每天有3班航班。 （所以共有12個航班）。

我們希望：

• 最大化，在飛行打對方唯一的玩家數量，
• 但也希望儘量減少（2名球員打得比一次對方更多雙OCCURENCES數量）。

由於每個航班有12名玩家和4名玩家，我可以每天每個航班大致創建36k玩家組合，因此它變得非常計算密集。有沒有更聰明的方法來解決這個問題？我的直覺告訴斐波那契可以提供幫助，但不知道具體如何。

這是我的代碼至今：

import random 
import itertools 
import pandas as pd  

def make_player_combi(day): 
    player_combis = [] 
    for flight in day: 
     #print flight 
     for c in itertools.combinations(flight,2): 
      combi = list(sorted(c)) 
      player_combis.append('-'.join(combi)) 
    return player_combis 

def make_score(a,b,c): 
    df = pd.DataFrame(a + b + c,columns=['player_combi'])['player_combi'] 
    combi_counts = df.value_counts() 
    pairs_playing = len(combi_counts) 
    double_plays = combi_counts.value_counts().sort_index() 
    return pairs_playing, double_plays 

players = ['A','B','C', 'D', 'E', 'F', 'G', 'H', 'I', 'J','K','L'] 

available_players = players[:] 
n = 0 
combinations_per_day = [] 

for players_in_flight_1 in itertools.combinations(players,4): 
    available_players_flight_1 = players[:] 
    available_players_flight_2 = players[:] 
    available_players_flight_3 = players[:] 

    for player in players_in_flight_1: 
     # players in flight1 can no longer be used in flight 2 or 3 
     available_players_flight_2.remove(player) 
     available_players_flight_3.remove(player) 


    for players_in_flight_2 in itertools.combinations(available_players_flight_2,4): 
     players_in_flight_3 = available_players_flight_3[:] 
     for player in players_in_flight_2: 
      players_in_flight_3.remove(player) 
     n = n + 1 
     print str(n), players_in_flight_1,players_in_flight_2,tuple(players_in_flight_3) 
     combinations_per_day.append([players_in_flight_1,players_in_flight_2,tuple(players_in_flight_3)]) 

n_max = 100 # limit to 100 entries max per day to save calculations 
winning_list = [] 
max_score = 0 
for day_1 in range(0,len(combinations_per_day[0:n_max])): 
    print day_1 
    for day_2 in range(0,len(combinations_per_day[0:n_max])): 
     for day_3 in range(0,len(combinations_per_day[0:n_max])): 
      a = make_player_combi(combinations_per_day[day_1]) 
      b = make_player_combi(combinations_per_day[day_2]) 

      x,y = make_score(a,b,c) 
      if x >= max_score: 
       max_score = x 
       my_result = {'pairs_playing' : x, 
          'double_plays' : y, 
          'max_day_1'  : day_1, 
          'max_day_2'  : day_2, 
          'max_day_3'  : day_3 
          } 
       winning_list.append(my_result) 

Answer 1

我選擇次優的（但不夠好）解決方案通過運行5個MIO樣品，並採取最低的結果......感謝所有一起

思考

Answer 2

你可以通過消除對稱性來蠻力。讓我們打電話給12位玩家a,b,c,d,e,f,g,h,i,j,k,l，寫一個連接4位玩家的航班：degj，以及三天航班的一天計劃：例如： abcd-efgh-ijkl。

第一天的航班武斷說，3個航班abcd-efgh-ijkl。

在第二天和第三天，你比少（12選4）*（8選4）的可能性，因爲計算每個不同的時間表6倍。例如，abcd-efgh-ijkl,efgh-abcd-ijkl和ijkl-efgh-abcd都被視爲單獨的，但它們本質上是相同的。事實上，你有（12選4）*（8選4）/ 6 = 5775不同的時間表。

總的來說，這爲您提供了5775 * 5775 = 33350625，可管理在3300萬至檢查。

我們可以做得更好一點：我們不妨假設，第2天和第3天的日程安排是不同的，不能算是相同的，但第2天及的被交換過3天的日程安排。這給了我們非常近2

另一個因素這裏的代碼，不會所有：

import itertools 
import collections 

# schedules generates all possible schedules for a given day, up 
# to symmetry. 
def schedules(players): 
    for c in itertools.combinations(players, 4): 
     for d in itertools.combinations(players, 4): 
      if set(c) & set(d): 
       continue 
      e = set(players) - set(c) - set(d) 
      sc = ''.join(sorted(c)) 
      sd = ''.join(sorted(d)) 
      se = ''.join(sorted(e)) 
      if sc < sd < se: 
       yield sc, sd, se 

# all_schedules generates all possible (different up to symmetry) schedules for 
# the three days. 
def all_schedules(players): 
    s = list(schedules(players)) 
    d1 = s[0] 
    for d2, d3 in itertools.combinations(s, 2): 
     yield d1, d2, d3 

# pcount returns a Counter that records how often each pair 
# of players play each other. 
def pcount(*days): 
    players = collections.Counter() 
    for d in days: 
     for flight in d: 
      for p1, p2 in itertools.combinations(flight, 2): 
       players[p1+p2] += 1 
    return players 

def score(*days): 
    p = pcount(*days) 
    return len(p), sum(-1 for v in p.itervalues() if v > 1) 

best = None 
for days in all_schedules('abcdefghijkl'): 
    s = score(*days) 
    if s > best: 
     best = s 
     print days, s 

它仍然需要一些時間來運行（約10-15我的電腦上分鐘），併產生本作輸出的最後一行：

abcd-efgh-ijkl abei-cfgj-dhkl abhj-cekl-dfgi (48, -3) 

這意味着有超過48個三天獨特的配對，並有3雙誰打一次（ab，fg和kl）彼此之間多。

注意，每個三對誰打對方不止一次打對方的每一天。這是不幸的，也許意味着你需要調整你如何計分時間表的想法。例如，不包括時間表，其中在同一對起着兩倍以上，並考慮玩家每個玩家看到數的軟分鐘，給出了這樣的解決方案：

abcd-efgh-ijkl abei-cfgj-dhkl acfk-begl-dhij 

這具有45個獨特配對，和9成對不止一次地玩對方。但是每個玩家至少會遇到7個不同的玩家，並且在實踐中可能更適合上述「最佳」解決方案。