组合算法分配人组 [英] Combinatorial algorithm for assigning people to groups

问题描述

一个同事来找我有一个有趣的问题，实际是具有做一个新城里人组她的一部分。

A coworker came to me with an interesting problem, a practical one having to do with a "new people in town" group she's a part of.

18位朋友想在晚饭组对每个接下来的4天。规则如下：

18 friends want to have dinner in groups for each of the next 4 days. The rules are as follows:

1. 每个天的组将分成4组，每组4，和一组2。
2. 在任何给定的一对人只会看到对方最多一次超过4天的课程。
3. 在任何给定的人只会是规模2组的一部分，最多一次。

一个强力递归搜索组分配的有效组显然是不切实际的。我扔在了树的修剪部分一些简单的逻辑，尽快，但还不足以让它的实用性。

A brute force recursive search for a valid set of group assignment is obviously impractical. I've thrown in some simple logic for pruning parts of the tree as soon as possible, but not enough to make it practical.

其实，我开始怀疑，这可能是不可能的遵守所有的规则，但我不能想出为什么这将是一个组合的说法。

Actually, I'm starting to suspect that it might be impossible to follow all the rules, but I can't come up with a combinatorial argument for why that would be.

有什么想法？

推荐答案

16的朋友可以预定4×4 4晚使用两个的相互正交的拉丁方秩序4.分配给每个朋友在4x4网格中一个鲜明的定位。在第一个晚上，组按行。在第二，组用柱。在第三组由拉丁广场＃1类似的条目（卡等级在4×4的例子）。在第四组由拉丁广场＃2类似的条目（牌西服在4×4的例子）。事实上，在仿射平面施工产生了三个相互正交的拉丁方，所以第五个晚上可以安排，确保每对朋友遇到一次。

16 friends can be scheduled 4x4 for 4 nights using two mutually orthogonal latin squares of order 4. Assign each friend to a distinct position in the 4x4 grid. On the first night, group by row. On the second, group by column. On the third, group by similar entry in latin square #1 (card rank in the 4x4 example). On the fourth, group by similar entry in latin square #2 (card suit in the 4x4 example). Actually, the affine plane construction gives rise to three mutually orthogonal latin squares, so a fifth night could be scheduled, ensuring that each pair of friends meets exactly once.

也许为16的时间表可以扩展，使用未使用的第五个晚上的自由度。

Perhaps the schedule for 16 could be extended, using the freedom of the unused fifth night.

编辑：这里的16人超过5晚的时间表。每一行是一个晚上。每一列是一个人。该条目是它们正在分配的组

here's the schedule for 16 people over 5 nights. Each row is a night. Each column is a person. The entry is the group to which they're assigned.

[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]

这篇关于组合算法分配人组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！