分组组合算法

Question

我的侄子有了一家新公司，它将商务人士团结在一起，一起喝咖啡，聊天。有点像音乐椅。在一段时间后，每个人都会站起来，然后移动到不同的桌子上。这个想法是，每个人都必须有机会与每个人交谈。他正在试图弄清楚如何在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张桌子，那么两个人将多次坐在同一张桌子上。当然，算法的思想是让每个人在最短的步骤中至少相遇一次。

Answer 1

这称为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

这个问题通常是非常困难的；解决方案要么通过不适用于所有参数设置的数学构造找到，要么通过冗长的约束满足计算找到。

Answer 2

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

Answer 3

这是您正在寻找的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分钟的会话。

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分钟的时间范围内进行15次会议，每次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.