用于将人员分配到组的组合算法

Question

一位同事带着一个有趣的问题来找我,一个实际的问题与她所参与的"城里新人"小组有关.

18位朋友希望在接下来的4天里分别为小组共进晚餐.规则如下:

1. 每天该小组将分成4组,每组4人,一组2人.
2. 任何一对人在4天的过程中最多只会见一次.
3. 任何给定的人最多只能参加一次2人组.

对一组有效的组分配进行强力递归搜索显然是不切实际的.我已经抛出一些简单的逻辑来尽快修剪树的部分,但还不足以使它变得实用.

实际上,我开始怀疑遵循所有规则可能是不可能的,但我无法提出一个组合论证,为什么会这样.

有什么想法吗？

Answer 1

使用两个相互正交的 4 阶拉丁方格可以安排 16 位朋友 4x4 共 4 个晚上。将每个朋友分配到 4x4 网格中的不同位置。第一天晚上，按行分组。第二个，按列分组。第三个，按拉丁方块 #1 中的相似条目进行分组（4x4 示例中的卡片等级）。第四个，按拉丁方块 #2 中的类似条目进行分组（4x4 示例中的卡片套装）。实际上，仿射平面构造产生了三个相互正交的拉丁方格，因此可以安排第五个晚上，确保每对朋友恰好见面一次。

也许可以利用第五晚未使用的自由时间来延长 16 日的行程。

编辑：这是 16 人 5 晚的日程安排。每一行都是一个晚上。每列都是一个人。该条目是他们被分配到的组。

[0, 0, 0, 0,  1, 1, 1, 1,  2, 2, 2, 2,  3, 3, 3, 3]
[0, 1, 2, 3,  0, 1, 2, 3,  0, 1, 2, 3,  0, 1, 2, 3]
[0, 1, 2, 3,  1, 0, 3, 2,  2, 3, 0, 1,  3, 2, 1, 0]
[0, 2, 3, 1,  1, 3, 2, 0,  2, 0, 1, 3,  3, 1, 0, 2]
[0, 3, 1, 2,  1, 2, 0, 3,  2, 1, 3, 0,  3, 0, 2, 1]