分组组合算法

我的侄子有一个新的业务，联合商务人士喝咖啡和谈话。这有点像音乐椅。经过一定的时间后，每个人都会选择不同的表格。这个想法是，每个人都必须有机会与每个人交谈。他试图弄清楚如何与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

分组组合算法

回答

相关问题