创建不具有多个相交元素的组合
我希望创建一种特殊类型的组合，其中没有两个集合超过一个相交元素。让我举个例子来解释一下：
假设我们有9个字母集，其中包含A、B、C、D、E、F、G、H和I
如果您创建三个字母的标准非重复组合，您将拥有9C3集合。这些将包含像ABC，ABD，BCD等集。我希望创建集，最多只有1个常见的字母。因此，在本例中，我们将获得以下集合：
ABC、ADG、AEI、AFH、BEH、BFG、BDI、CFI、CDH、CEG、DEF和GHI -请注意，如果取任意两个集合，则重复字母不超过1个。
什么是生成这样的集合的好方法？它应该是可扩展的解决方案，以便我可以为1000个字母的集合，与子集的大小为4。
任何帮助都是非常感谢的。
谢谢
回答 1
Stack Overflow用户
发布于 2010-06-04 09:41:44
我不得不添加另一个答案，因为另一个已经太长了。
如果您有以下约束：
1)你需要每周4人一组。
2)某一周的每一组是不相交的，每个学生恰好属于一组。
3)如果两个学生在同一个组中，将来他们需要不能在一个组中。
如果你像下面这样构造一个图G：
1)每个学生都是一个节点。
2)两个学生被一条边连接在一起，如果他们以前没有在一起过。
随着学生的随意放弃/加入，这成为一个困难的问题！即使你一开始就有一个完整的图表，几周后，这个图表可能会变得非常不可预测。
你的问题:你需要找到G的一个生成子图，这样它就是K_4副本的并集，或者换句话说，是K_4s中的一个分区。
不幸的是，这个问题看起来是NP-难的:4-集合的精确覆盖(这是NP-完全的)可以归结为您的问题(就像3-集合的精确覆盖可以简化为三角形划分一样)。
也许这将有助于给出一些近似算法：http://www.siam.org/proceedings/soda/2010/SODA10_122_chany.pdf
(您的问题可以简化为Hypergraph匹配，因此算法可以用于您的问题)。
确切的封面：http://en.wikipedia.org/wiki/Exact_cover
划分为三角形：https://noppa.tkk.fi/noppa/kurssi/t-79.5103/viikkoharjoitukset/T-79_5103_solutions_5.pdf
4集的精确覆盖=给定大小为4m的集合S和S的4元素子集的集合C，是否存在C的子集C‘，使得S的每个元素在C’中恰好出现一次。
不幸的是，看起来您可能需要更改一些约束。
https://stackoverflow.com/questions/2955318
复制相似问题