3

我的侄子有一项新业务，该业务将商务人士团结起来喝咖啡和交谈。这有点像音乐椅。在给定的时间后，每个人都起身到不同的桌子上。这个想法是每个人都必须有机会与每个人交谈。他试图弄清楚如何使用 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 张桌子，那么会有两个人不止一次坐在同一张桌子上。当然，算法的想法是让每个人在最短的步骤中至少见面一次。

4

3 回答 3

8

这被称为社交高尔夫球手问题。该链接指向 16 人、4 桌案例的解决方案，在此处复制。

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

这个问题一般来说非常难；通过不适用于所有参数设置的数学结构或通过冗长的约束满足计算来找到解决方案。

于 2013-05-12T21:18:28.713 回答
1

Pé，我看到你也对 APL 感兴趣，所以你可能喜欢一个 APL 算法来做到这一点：

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

于 2013-06-26T04:55:40.300 回答
0

这是您正在寻找的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.
于 2013-12-22T14:50:15.490 回答