分组组合算法

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张桌子，那么会有两个人坐在同一张桌子上超过一次。当然，算法的目的是让每个人在最短的步骤中至少见面一次。

- Expedito

Answer 1

这被称为社交高尔夫问题。链接指向16人、4桌情况的解决方案，此处再次复制。

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

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

- David Eisenstat

Answer 2

Pé，我看到你也对APL感兴趣，所以你可能会喜欢一个APL算法来完成这个任务：

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

- MBaas

---

谢谢！我本来打算自己找解决方案，但我会去看看那个。当我试着用PHP解决它时，我不得不找一个位运算算法去扩展。所以当我开始学习APL时，我很高兴发现扩展已经内置了。 - Expedito

哦，我一定是在 HPH 中做这件事情很痛苦！这就是为什么我如此喜欢 APL :) - MBaas

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分钟的会议。所有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秒的时间框架内进行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.

- Bob R