我希望创建一种特殊类型的组合,其中没有两个集合超过一个相交元素。让我举个例子来解释一下:
假设我们有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。
任何帮助都是非常感谢的。
谢谢
发布于 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
复制相似问题