创建有没有更多的1相交的元素组合 [英] Creating combinations that have no more one intersecting element

问题描述

我希望创造一种特殊类型的组合，其中无两套有一个以上的交叉元素。让我用一个例子说明：

I am looking to create a special type of combination in which no two sets have more than one intersecting element. Let me explain with an example:

让我们说，我们有一个包含A，B，C，D，E，F，G，H 9信集，我

Let us say we have 9 letter set that contains A, B, C, D, E, F, G, H, and I

如果您创建三个字母的标准不重复的组合，你将有9C3套。 这些将包含台像ABC，ABD，BCD等我期待创建具有至多只有1常见的字母集。因此，在这个例子中，我们会得到以下几组：

If you create the standard non-repeating combinations of three letters you will have 9C3 sets. These will contain sets like ABC, ABD, BCD, etc. I am looking to create sets that have at the most only 1 common letter. So in this example, we will get following sets:

ABC，ADG，AEI，AFH，BEH，BFG，BDI，CFI，鼎晖，CEG，DEF和GHI - 请注意，如果你采取任何两套有不超过1重复信

ABC, ADG, AEI, AFH, BEH, BFG, BDI, CFI, CDH, CEG, DEF, and GHI - note that if you take any two sets there are no more than 1 repeating letter.

什么将是一个很好的方式产生这种集？它应该是可扩展的解决方案，这样我可以做一组1000信件，以4分集大小。

What would be a good way to generate such sets? It should be scalable solution so that I can do it for a set of 1000 letters, with sub set size of 4.

任何帮助是非常AP preciated。

Any help is highly appreciated.

感谢

推荐答案

我不得不添加另一个答案，另一次是太长了。

I had to add another answer as the other one was too long already.

如果您有以下限制：

1）需要4组每星期。

1) You need groups of 4 every week.

2）每一组中的某一周是不相交的，每个学生在正好一个组。

2) Each group in a certain week is disjoint and each student is in exactly one group.

3）如果两个学生在同一组中，它们需要不能在同一组中的未来。

3) If two students are in the same group, they need cannot be in the same group in future.

如果您构建一个图G如下：

If you construct a graph G as follows:

1）每个学生都是一个节点。

1) Each student is a node.

2）两名学生通过边当且仅当他们没有在一起的一组前加入。

2) Two students are joined by an edge iff they haven't been together in a group before.

通过学生下探/任意加入，这将成为一个难题！即使你开始了一个完整的图形intially，几个星期后，该图将变得相当联合国predictable。

With students dropping/joining arbitrarily, this becomes a hard problem! Even though you start out with a complete graph intially, after some weeks, the graph could become quite unpredictable.

您的问题：你需要找到g的支撑子图，使得它K_4一个分区或者换句话说份的联合成K_4s

Your problem: You need to find a spanning subgraph of G, such that it is a union of copies of K_4 or in other words a partition into K_4s.

不幸的是，像这样的问题是NP硬：由4集的精确罩（这是NP完全）可以减少到您的问题（就像精确盖由3台可以减少到分割成三角形）

Unfortunately, look like this problem is NP-Hard: Exact cover by 4-sets (which is NP-Complete) can be reduced to your problem (just like Exact cover by 3-sets can be reduced to partition into triangles).

或许这将有助于给一些aproximation算法： HTTP：//www.siam .ORG /程序/苏打/ 2010 / SODA10_122_chany.pdf

Perhaps this will help give some aproximation algorithms: http://www.siam.org/proceedings/soda/2010/SODA10_122_chany.pdf

（您的问题可以减少到超图匹配和可用于您的问题，这样的算法为该）。

(Your problem can be reduced to Hypergraph matching and so algorithms for that can be used for your problem).

精确覆盖： http://en.wikipedia.org/wiki/Exact_cover

划分成三角形：的https://noppa.tkk.fi/noppa/kurssi/t-79.5103/viikkoharjoitukset/T-79_5103_solutions_5.pdf

精确封面=鉴于大小4米和为S 4-元素子集的集合℃的集合S，确实存在的C的子集C'，使得S中的每个元素出现precisely一次在C'。

Exact Cover by 4 sets = Given a set S of size 4m and a collection C of 4-element subsets of S, does there exist a subset C' of C, such that each element of S appears precisely once in C'.

不幸的是，好像你可能需要更改一些约束。

Unfortunately, seems like you might have to change some constraints.

这篇关于创建有没有更多的1相交的元素组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！