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

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 在下面指出的那样，在此示例中有不同的分区方式。但是，分区一次后，就不会再有第二次拆分将所有项目对分开。那是很好——我的应用程序不需要生成所有可能的全局分区集方法，一个满足约束的解决方案就可以了)}

---

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

到目前为止，我一直将其视为 exact cover问题，并用 backtracking algorithm 解决它(DLX 的变体)。这对于成对非常有效，但随着组变大，算法必须考虑的可能性数量激增，处理变得非常笨重。

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

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

非常欢迎任何想法和建议。 非常感谢您考虑这一点!

---

更新

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

我发现的最好的资源之一，我想在这里分享，是 Markus Triska 的工作。 ，他在论文中讨论了几种方法(然后继续介绍了一个非常好的算法)。如果有人遇到类似问题，强烈建议这样做!

Answer 1

这个问题的研究名称为 Social Golfer Problem .文献量很大，但主要有以下三种方法:

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

2. 完整的搜索方法，例如对精确覆盖的缩减。据我所知，这里的研究围绕对称性破缺的有效方法展开，其中您修复第一行的想法可能是最简单的。

3. 数学构造。当 q 是素数幂时，有一个构造 q 组 q 涉及 finite affine planes这并不太难实现。除此之外，还有很多一次性的建筑。 《组合设计手册》可能是总结已知知识的最佳选择。