分組組合算法

我的侄子有一個新的業務，聯合商務人士喝咖啡和談話。這有點像音樂椅。經過一定的時間後，每個人都會選擇不同的表格。這個想法是，每個人都必須有機會與每個人交談。他試圖弄清楚如何與16人和4張桌子一起移動5次。分組組合算法

我想找出一個算法來做到這一點，但我發現這個問題比我最初想象的要困難得多。爲了簡化它，我制定瞭如何與6人和3張桌子做到這一點。

Step 1: (1, 2), (3, 4), (5, 6) 
Step 2: (1, 3), (2, 5), (4, 6) 
Step 3: (1, 4), (2, 6), (3, 5) 
Step 4: (1, 5), (2, 4), (3, 6) 
Step 5: (1, 6), (2, 3), (4, 5)

一種可能性，這不會是非常有效的，將生成的所有可能的組合，並消除任何互相排斥的：它可以如下表示。然而，奇怪的組合，這是不可能的。例如，如果有6個人只有2張桌子，則會有兩個人不止一次坐在同一張桌子上。當然，該算法的思想是讓每個人都以最短的步驟達到至少一次。

來源

2013-05-12 Pé de Leão

這被稱爲social golfer problem。鏈接轉到了一個解決方案，爲16人，4表案，轉載在這裏。

ABCD EFGH IJKL MNOP 
AEIM BFJN CGKO DHLP 
AFKP BELO CHIN DGJM 
AGLN BHKM CEJP DFIO 
AHJO BGIP CFLM DEKN

這個問題一般很難;解決方案可以通過不適用於所有參數設置的數學結構或冗長的約束滿足度計算來找到。

來源

2013-05-12 21:18:28

PE，我看見你也有興趣在APL，所以你可能會喜歡的APL算法來做到這一點：

http://dfns.dyalog.com/n_pmat.htm

來源

2013-06-26 04:55:40 MBaas

謝謝！我試圖找到我自己的解決方案，但我會檢查。試圖用PHP來解決這個問題，我不得不尋找一種擴展的按位算法。所以當我開始學習APL時，我很高興地發現擴展已經建成了。 – 2013-06-26 08:42:43

呵呵，我一定很難在HPH中做到這一點！這就是我非常喜歡APL的原因:) – MBaas 2013-06-26 15:27:13

這裏是你在找什麼的6人組。 ..

Session 1 Table 1 #1 & #6 
Session 1 Table 2 #2 & #5  
Session 1 Table 3 #3 & #4 

Session 2 Table 1 #2 & #3 
Session 2 Table 2 #6 & #4 
Session 2 Table 3 #5 & #1 

Session 3 Table 1 #3 & #5 
Session 3 Table 2 #4 & #1 
Session 3 Table 3 #6 & #2 

Session 4 Table 1 #2 & #4 
Session 4 Table 2 #1 & #3  
Session 4 Table 3 #5 & #6 

Session 5 Table 1 #4 & #5 
Session 5 Table 2 #3 & #6 
Session 5 Table 3 #1 & #2

複製&列表上方粘貼到自己的字處理器，然後使用搜索和替換的數字更改爲名稱。

如果他們每週見面一次，則需要5周才能見面一次。如果他們一天見面，每次會議持續15分鐘，您需要5-15分鐘的會議（1小時&總共15分鐘）。您還可以爲每個會議添加日期，時間和地點。如果您的會議持續時間超過5周，只需複製堆棧再進行5周的會話。

對於16人組，並且所有16人都會見其他15人一次，您需要8個桌子並可以使用10或15分鐘的會話。所有16個人將與其他15位參與者一對一會面。第一和第二屆會議應該是這樣的：

Session 1 Table 1 #1 & #2 
Session 1 Table 2 #3 & #4 
Session 1 Table 3 #5 & #6 
Session 1 Table 4 #7 & #8 
Session 1 Table 5 #9 & #10 
Session 1 Table 6 #11 & #12 
Session 1 Table 7 #13 & #14 
Session 1 Table 8 #15 & #16 

Session 2 Table 1 #10 & #5 
Session 2 Table 2 #4 & #1 
Session 2 Table 3 #2 & #6 
Session 2 Table 4 #12 & #7 
Session 2 Table 5 #8 & #3 
Session 2 Table 6 #14 & #9 
Session 2 Table 7 #16 & #11 
Session 2 Table 8 #13 & #15 

Continues Sessions 3 thru 15

的16人輪換組是相當大的。會議時間可以是減少到10分鐘，這需要在2:30分鐘的時間範圍內每個10分鐘的10分鐘，或者分散兩天或更多天。建立輪換計劃後，最後一件事是使用全局搜索&替換實際的名稱。光標在列表頂部搜索＃1並替換爲Bill Jones。對其他人也一樣。

有很多方法可以重新安排日期，16元素的時間元素循環賽團隊建設計劃如此。以下是單線完成的示例。

Dec 16 Monday 
Session 1 Table 1 9:00am Bill Jones & Fred Johnson 
Session 1 Table 2 9:00am Jack Wilson & Sarah Ford 
Session 1 Table 3 9:00am Larry Peterson & Sue Falvey 
etc.

來源

2013-12-22 14:50:15

分組組合算法

回答

相關問題