把14个人分成4组，使每个人至少见面一次。

Question

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

奇怪的是，这不是一个家庭作业问题，但一个家庭成员正试图组织一个变焦电话，作为一个数学学生，它让我感兴趣。我环顾四周，发现这篇文章尝试了类似的东西(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.)，但我仍然不确定。)我得到了一些真正杂乱无章的涂鸦，现在我无法破译。

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操作(不管这对是在组中还是在另一个组中的中)。

由于我们希望表示所有的对，所以我们希望选择一个可能的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]]]].

正如您所看到的，组合是巨大的，43,051,823,251,587,106,104,672,087,435,021,150 = C_16_1001，所以上面的循环可能不会在合理的时间内实现，在这个阶段，我们甚至不知道是否有一个有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组中完成。