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

Question

我想做的是将一组（n）个项目分成大小相等的组（大小为[的组=52=]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 在下面指出的那样，在此示例中有不同的分区方式。但是，分区一次后，再也没有第二次拆分保留所有对项目分开。这很好——我的应用程序不需要生成所有可能的方式来全局划分集合，一个满足约束的解决方案就可以）}

我现在的问题是：有没有办法有效地做到这一点？有什么技巧可以加快这些集合的生成速度吗？

到目前为止，我一直将其视为 exact cover problem, and solving it with a backtracking algorithm（DLX 的变体）。这对成对非常有效，但随着组变大，算法必须考虑的可能性数量激增，处理变得非常笨重。

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

优化和启发式减少解决之前需要考虑的可能性的数量（例如，从上面的示例中可以清楚地看出，可以进行第一次拆分简单任意，每个分区的第一组[上面第一列]可以自动生成）。
是否有可以应对大量候选人的回溯变体？（即不需要事先生成所有可能性）
我应该考虑的其他算法、方法或数学概念？

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

更新

好的，这已经有一段时间了，但我在这上面花了很多时间，想回复你。 @david-eisenstat 通过给我正确的搜索词让我走上了正确的道路（非常感谢！）——我已经阅读了很多关于 Social Golfer Problem 的文章。

我发现的最好的资源之一，我想在这里分享，是 Markus Triska 的工作，他在他的论文。如果有人遇到类似问题，强烈建议这样做！

Answer 1

假设 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

可能的分区数随着组长度的平方而减少。这意味着，没有太多可能的分区:-)

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

Answer 2

这个问题是在 Social Golfer Problem 下研究的。文献量很大，但主要有以下三种方法：

本地搜索方法，可以处理很多对不存在的情况。
完整的搜索方法，如您减少到精确覆盖。据我所知，这里的研究围绕对称性破缺的有效方法展开，其中你修复第一行的想法可能是最简单的。
数学结构。当 q 是素数幂时，q 的 q 组涉及 finite affine planes 的构造并不太难实现。除此之外，还有很多一次性的建筑。组合设计手册可能是总结已知知识的最佳选择。

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

How to (efficiently) generate disjoint sets while usings pairs of elements only once?

algorithm

combinatorics

solver

constraint-programming

disjoint-sets