如何（高效地）生成互不相交的集合，同时仅使用每对元素一次？

Question

我想做的是将一组（n）项分成相等大小的组（m），并且为了简单起见，假设没有剩余，即n可被m整除。多次这样做，我想确保没有一对物品两次在同一组中。

为了让这个问题更具体化，在六个项目A..F中构建两个组，可以使用不同的方式将集合分区五次：

- (A, B), (C, D), (E, F) - (A, C), (B, E), (D, F) - (A, D), (B, F), (C, E) - (A, E), (B, D), (C, F) - (A, F), (B, C), (D, E)

同一组物品只能被分成三组，且不重叠:

• (A, B, C), (D, E, F)

_{（正如@DavidHammen在下面指出的那样，这个例子有不同的分割方式。然而，一旦进行了划分，就再也没有另一个第二次划分可以使所有物品对保持分开。这很好——我的应用程序不需要生成全局所有可能的划分方式，符合约束条件的一个解决方案就可以）}

---

我的问题是：有没有一种高效的方法来完成这个任务？有什么技巧可以加快生成这些集合的速度？

到目前为止，我一直将其视为一个精确覆盖问题，并使用回溯算法（DLX的变体）来解决它。对于成对的情况，这种方法非常有效，但随着组的规模变大，算法需要考虑的可能性数量激增，处理起来非常棘手。

我正在寻找加速处理的技巧。任何想法都非常受欢迎，特别是（但不限于）：

• 优化和启发式算法，以减少在解决之前需要考虑的可能性数量（例如，从上面的示例中可以清楚地看出，第一个分割可以简单地任意选择，并且每个分区的第一组[上面的第一列]可以自动生成）。
• 是否有backtracking的变体可以处理大量的候选项？（即不需要预先生成所有可能性）
• 我应该考虑其他算法、方法或数学概念吗？

欢迎提出任何想法和建议。非常感谢您的考虑！

---

更新

好的，这已经有一段时间了，但我花了更多的时间在这上面，并想要回复你。@david-eisenstat 给了我正确的搜索词（非常感谢！）——我后来阅读了很多关于社交高尔夫问题的内容。

其中我发现的最好的资源之一是Markus Triska的作品，他在论文中讨论了几种方法（然后继续介绍了一个非常好的算法）。如果有人遇到类似的问题，强烈推荐阅读！

- mezzopiano

---

同一个集合的项只能被分成最多三个组，而且不能有重叠对：((A B D), (C E F))和((A B E) (C D F))还有至少六个组合为什么不行？问题陈述并没有明确说明你为什么排除了那些组合。 - David Hammen

@DavidHammen，根据OP的问题描述，A和B这一对出现在两个分区中都属于同一组。同时问题中也指出，没有任何一对项目会在同一组中出现两次。 - A.S.H

非常感谢你们两位！@DavidHammen：你完全正确，我可以使用你提供的任何一个例子，而不是我给出的那个。我会在问题中进行澄清。 - mezzopiano

@a-s-h：你完全理解我的意图，感谢你的澄清！再次感谢你的努力和思考这个问题。 - mezzopiano

您可能想搜索以下关键词：组合设计，正交阵列。 - jkff

@jkff 谢谢！你的指针非常有帮助，您是否可以稍微扩展一下您的评论并提供答案？我在过去几天里一直在研究组合数学，并发现了一些与我的问题相似之处，但我从未遇到过组合设计领域。我是否正确地认为我正在寻求的是“成对平衡设计”？您是否知道这个领域中对计算机科学家有用的任何资源或库？ - mezzopiano

Answer 1

这个问题被称为社交高尔夫球手问题。文献资料相当丰富，但主要有三种方法：

1. 局部搜索方法，可以处理许多配对不存在的情况。

2. 完全搜索方法，例如您的精确覆盖约简。从我记得的情况来看，这里的研究重点在于对称性破缺的高效方法，其中您固定第一行的想法可能是最简单的。

3. 数学构造。当q是素数幂时，有一个涉及有限仿射平面的q个q组的构造不太难实现。除此之外，还有很多一次性的构造。《组合设计手册》可能是总结已知信息的最佳选择。

- David Eisenstat

---

哇，非常感谢您快速而全面的回答！您的指引对于寻找额外的文献和实现指针非常有帮助。我也看了《组合设计手册》，看起来我只能深入数学了 :-) 。目前我已经点赞了您的回答（希望我可以多次点赞），等我阅读完后会回来添加我的发现作为评论。 - mezzopiano

Answer 2

设 n=m*k，将其分为 m 组，每组有 k 个项目。

经过 x 次分组后，每个项目与其他 x*(k-1) 个项目在同一组中。在创建了 t-1 个分组后，在下一个分组中，A 可以选择：

second element : n -   (t-1)*(k-1)   - 1  items
third element  : n - 2*(t-1)*(k-1)   - 2  items
fourth element : n - 3*(t-1)*(k-1)   - 3  items
...
k'th element   : n -   (t-1)*(k-1)^2 - (k-1)  items

要创建第 t'th 个分区，我们需要：

n - (t-1)*(k-1)^2 - (k-1) > 0
=>
t < (n - k + 1) / ((k-1)^2) + 1

可能的分区数量随着组长度的平方而减少。这意味着可能的分区不是太多了 :-)

我会采用一些贪心的方法。为每个项目存储可用的项目集，并通过将第一个可用项目添加到组中来创建新的分区。

- Ante