algorithm - 将 14 人分成 4 人一组，每个人至少见面一次

Question

我的一个房间里有 14 个人，房间中间有一张 table 和 4 张椅子。我希望每个人至少与其他人一起坐在 table 边一次(即，他们以 4 人为一组，与房间里的其他人一起坐在 table 边)。我想知道我需要的最小组数是多少以及如何通过算法找到这些组。

奇怪的是，这不是一个家庭作业问题，但一位家庭成员正在尝试组织一次 Zoom 通话，作为一名数学学生，我对此很感兴趣。我环顾四周，发现这篇文章尝试了类似的东西( http://zulko.github.io/blog/2013/11/08/placing-your-employees-so-that-everyone-meets/ )，并考虑了社交高尔夫球手问题( https://www.metalevel.at/sgp/#:~:text=The%20Social%20Golfer%20Problem%20(SGP,denoted%20by%20the%20triple%20g%2Dp%2Dw.) 但我仍然不确定。我得到了 23~ 一些非常杂乱的纸质涂鸦，但我现在不能破译。

Answer 1

您有 C_4_14 种可能的组合 (14*13*12*11/(4*3*2*1)) = 1001可能为 4 人一组。

您需要确保拥有所有可能的对 C_2_14 14*13/(2*1) = 91对。

每组 4 人，您有 C_2_4 = 6 对。

让我们为每个可能的对分配一个位(我们需要一个 91 位整数)。
现在，每组 4 个都可以写为 91 位整数签名，仅用 6 位集表示 6 对。

现在的问题是组装这些组，以便每对至少代表一次。
这相当于 bitOr 运算(无论该对是否在一个组中 OR 在另一个组中)。
由于我们希望所有对都被表示，因此我们希望选择可能的 1001 个组中的一个子集，使得该子集的 bitOr 为 2^91-1(所有对至少被表示一次)。

由于我们有 91 对，每组 6 对，6*15 < 91 < 6*16 ，这给了我们一个下限:我们至少需要 16 组 4 组才能实现这一点，也许更多。
最好的情况下，我们将有 5 对人会面两次，最糟糕的是，一对人会面 6 次。

为了解决这个问题，我们必须选择对的索引，例如:

(1,2) = 1
(1,3) = 2
...
(1,14) = 13
(2,3) = 14
...
(2,14) = 25
...
(13,14) = 91

这里是一个用于形成配对的 Squeak Smalltalk 代码示例

people := #(mary john clara tim julia mike vanessa bob jean harry kim donald morgan roy).
pairMap := Dictionary new: 91.
i := 0.
people combinations: 2 atATimeDo: [:p |
    pairMap at: p copy put: (i := i+1)].

现在，对于每四人一组，我们可以关联配对签名:

quadMap := Dictionary new: 1001.
iQuadMap := Dictionary new: 1001.
people combinations: 4 atATimeDo: [:q | | j |
    j := 0.
    q combinations: 2 atATimeDo: [:p| j := j bitAt: (pairMap at: p) put: 1].
    quadMap at: q copy put: j.
    iQuadMap at: j put: q copy].

一个非常简单的解决方案可能是枚举 nGroup 四边形的组合，直到找到覆盖所有对的组合。 nGroup 将从 16 开始。

allPairs := 1<<91-1.
16 to: 91 do: [:nGroup |
    quadMap values combinations: nGroup atATimeDo: [:g |
        (g reduce: #bitOr:) = allPairs ifTrue: [^g collect: [:signature | iQuadMap at: signature]]]].

正如你所看到的，组合是巨大的，C_16_1001 = 43,051,823,251,587,106,104,672,087,435,021,150所以上面的循环可能无法在合理的时间内实现，并且在这个阶段我们甚至不知道是否有16组的解决方案!

我们可以尝试一些简单的贪婪算法:选择下一组作为迄今为止解决方案签名最大化位数(最小化重叠位)的一组。
可以通过 bitAnd 运算来计算重叠位

allPairs := 1<<91-1.
signatureSoFar := 0.
groups := OrderedCollection new.
[ signatureSoFar = allPairs]
    whileFalse:
        [heap := Heap withAll: quadMap values sortBlock: [:x | (x bitAnd: signatureSoFar ) bitCount] ascending.
        groups add: heap first.
        signatureSoFar := signatureSoFar bitOr: heap first].
^groups collect: [:qSig | iQuadMap at: qSig]

运行此命令可以在几毫秒内提供 18 个组的解决方案...
使用打乱的值运行贪婪算法 10000 次并没有给出更短的解决方案(找到的解决方案在 18 到 20 组之间)。

由您决定是否可以在少于 18 个组中完成此操作。