algorithm - 创建没有一个相交元素的组合

Question

我希望创建一种特殊类型的组合，其中没有两个集合具有多个相交元素。让我举例说明：
假设我们有9个字母集，包含a、b、c、d、e、f、g、h和i
如果您创建三个字母的标准非重复组合，您将拥有9C3集。
它们将包含ABC、ABD、BCD等集合。我希望创建最多只有一个公共字母的集合。在本例中，我们将得到以下集合：
abc、adg、aei、afh、beh、bfg、bdi、cfi、cdh、ceg、def和ghi—请注意，如果您选择任何两组，则不超过一个重复字母。
有什么好的方法可以生成这样的集合？它应该是一个可伸缩的解决方案，这样我就可以用1000个字母来完成，子集合大小为4。
任何帮助都是非常感谢的。
谢谢

Answer 1

我不得不补充另一个答案，因为另一个已经太长了。
如果有以下约束：
1）你每周需要4人一组。
2）某周内每组不相交，每个学生正好在一个组内。
3）如果两个学生在同一个组中，他们将来不需要在同一个组中。
如果按如下方式构造图g：
1）每个学生都是一个节点。
2）如果两个学生以前没有在一个小组中一起过，他们就被一个边缘连接起来。
随着学生的随意辍学/加入，这成为一个难题！即使你一开始就有一个完整的图表，几周后，图表可能会变得非常不可预测。
你的问题是：你需要找到一个g的生成子图，这样它就是k~4副本的并集，或者换句话说就是k~4的一个分区。
不幸的是，看起来这个问题是np难的：4集的精确覆盖（这是np完全的）可以简化为您的问题（就像3集的精确覆盖可以简化为划分成三角形）。
也许这将有助于给出一些近似算法：http://www.siam.org/proceedings/soda/2010/SODA10_122_chany.pdf
（你的问题可以简化为超图匹配，因此算法可以用于你的问题）。
准确封面：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的4个元素子集的集合C，是否存在C的子集C′，使得S中的每个元素在C′中精确地出现一次。
不幸的是，似乎你必须改变一些限制。