将 14 人分成 4 人一组，使每个人至少满足一次

Question

我一个房间有 14 个人，房间中间有一个 table 有 4 把椅子。我希望每个人至少与其他人一起坐在 table 一次（即，他们通过与他们一起坐在 table 处，以 4 人一组的方式与房间里的每个人见面）。我想知道我需要的最少组数是多少，以及如何通过算法找到这些组。

奇怪的是，这不是家庭作业问题，而是一位家庭成员正试图组织一次 zoom 通话，作为一名数学专业的学生，它引起了我的兴趣。我环顾四周，发现这篇文章尝试了类似的东西（http://zulko.github.io/blog/2013/11/08/placing-your-employees-so-that-everyone-meets/) and considered the social golfer problem (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 对。

现在的问题是 assemble 组，这样每对至少代表一次。
这相当于一个bitOr操作（不管pair是否在一个组中OR在另一个组中）。
并且由于我们希望所有对都被表示，所以我们希望从可能的 1001 个组中选择一个子集，使得该子集的 bitOr 为 2^91-1（所有对至少被表示一次）。

因为我们有 91 对，每组 6 对，6*15 < 91 < 6*16，这给了我们一个下限：我们至少需要 16 组，每组 4 对，也许更多。
最好的情况是5对人会面2次，最差的情况是1对人会面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 个组中完成。

将 14 人分成 4 人一组，使每个人至少满足一次

Arrange 14 people into groups of 4 such that every person meets once minimum

algorithm

math

combinatorics