我正在寻找一种特殊类型的组合，其中没有两个集合具有多个相交元素。让我用一个例子来解释：
假设我们有 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。
非常感谢任何帮助。
谢谢
假设您有 n 个字母（或学生，或其他），并且每周都希望将它们划分为大小为 k 的子集（n/k每周总共有子集）。这种方法几乎n/k每周都会生成子集——我在下面展示了如何扩展它以生成精确的n/k子集。
先挑p，最大素数<= n/k。
让我们考虑每个有序对 (a,b) 使得
0 <= a < k
0 <= b < p
我们可以将每一对映射到我们的一个字母；因此，我们可以p*k <= n用这种方式映射字母（再次，我将在下面展示如何精确映射 n 个字母）
(0,0) => 'A'
(0,1) => 'B'
...
(0,p-1) => 'F'
(1,0) => 'G'
(1,1) => 'H'
...
(k-1,p-1) => 's'
现在，给定
0 <= w < p
0 <= i < p
我们可以创建一个有序对的集合 S w (i)。S w (i)中的每一对将代表一个字母（根据我们上面的映射），而集合 S w (i) 本身代表一个“字母分组”，也就是。一个大小为 k 的子集。
S w (i)的公式为
S w (i) = {(0,i mod p), (1,(w+i) mod p), (2,(2w+i) mod p),..., ((k-1), ((k-1)*w+i) 模 p)}
= { (x,y) | 0 <= x < k 和 y = w*x + i (mod p)}
如果我们在所有可能的值上改变 w 和 i，我们得到 p 2 个总集合。当我们取其中任意两个集合时，它们最多有一个相交元素。
假设我们有两个集合 S w1 (i 1 ) 和 S w2 (i 2 )。如果 S w1 (i 1 ) 和 S w2 (i 2 ) 有多个共同的元素，则至少存在两个x使得
w 1 *x + i 1 = w 2 *x + i 2 (mod p) (w 1 -w 2 )*x + (i 1 -i 2 ) = 0 (mod p)
然而，任何学过模运算的人都知道，如果 p 是素数，要么 x 有唯一解，要么 (w 1 = w 2 and i 1 = i 2 ); 因此，x 不能超过一个，并且 S w1 (i 1 ) 和 S w2 (i 2 ) 最多可以有一个相交元素。
由于p < n/k，由切比雪夫定理（该定理表明 x > 3 时 x 和 2x 之间存在素数）
n/2k < p <= n/k
因此，此方法至少生成 (n/2k) 2个字母子集，尽管实际上 p 将更接近 n/k，因此该数字将更接近 (n/k) 2。由于最大可能此类子集的简单上限是n(n-1)/(k(k-1))（请参阅下面 BlueRaja 的评论），这意味着该算法是渐近最优的，并且将生成接近最优数量的集合（即使在最坏的情况下，它也不会生成少于大约是最佳数量的 1/4；再看下面的评论）
您现在希望每周将字母分组到分区中：每周，所有字母都恰好包含在一个组中。
我们通过让w固定为某个值（代表星期）并让i从 0 到 p-1 变化来做到这一点。
考虑我们创建的组：
S w (i) = { (x,y) | 0 <= x < k 和 y = w*x + i (mod p)}
假设w是固定的，i从 0 到 p-1 变化。然后我们得到 p 个集合：
S w (0), S w (1), ..., S w (p-1)
现在假设 S w (i 1 ) 和 S w (i 2 ) （与 i 1 =/= i 2）相交；然后
w*x + i 1 = w*x + i 2 (mod p)
对于某些 x，因此 i 1 = i 2。因此，S w (i 1 ) 和 S w (i 2 ) 不相交。
由于我们的集合中没有两个相交，并且它们中正好有 p 个（每个都有 k 个元素），所以我们的集合形成了 k*p 个字母的分区。
这种方法的最大缺点是它为 p*k 个字母而不是 n 个字母生成集合。如果不能省略最后一个字母（如您的情况，字母是学生），有两种方法可以每周准确生成 n/k 个子集：
求一组质数 p 1 , p 2 , p 3 , ... 总和正好为 n/k。然后我们可以将每组 p i k 个字母视为一个独立的字母表，这样我们就不是找到 p k 个字母的子集，而是找到一组 p 1 *k 个字母的子集，另一组 p 2 *k 个字母的子集, 另一组...
这样做的缺点是来自一个组的字母永远不会与来自另一组的字母配对，从而减少了生成的子集的总数。幸运的是，如果 n 是偶数，根据哥德巴赫猜想† 你最多只需要两个组（如果 n 是奇数，你最多只需要三个)
此方法保证大小为 k 的子集，但不会生成尽可能多的子集。
†虽然未经证实，但众所周知，您可能会遇到这个问题的每一个非常大的数字都是正确的
另一种选择是使用最小的素数 p >= n/k。这将为您提供 p*k >= n 个字母 - 在生成子集后，只需丢弃多余的字母。因此，最后这会为您提供一些大小 < k 的子集。假设 k 均分 n（即 n/k 是整数），您可以取较小的子集并手动将它们混合以制作大小为 k 的子集，但您可能会以这种方式与过去/未来的子集有一些重叠。
此方法至少生成与原始方法一样多的子集，但有些子集的大小可能 < k
取 n = 15, k = 3。即有 15 名学生，我们将三人一组。
首先，我们选择最大的素数 p <= n/k。n/k是素数（我们很幸运！），所以 p = 5。
我们将 15 个学生映射到上述的有序对 (a,b) 中，给出我们（每个字母是一个学生）：
(0,0) = A
(0,1) = B
(0,2) = C
(0,3) = D
(0,4) = E
(1,0) = F
(1,1) = G
(1,2) = H
(1,3) = I
(1,4) = J
(2,0) = K
(2,1) = L
(2,2) = M
(2,3) = N
(2,4) = O
该方法生成 25 组，每组 3 组。因此，由于我们需要每周安排 n/k = 5 组，我们可以安排 5 周的活动（每周 5 组 * 5 周 = 25 组）。
对于第 0 周，我们将分区生成为
S 0 (i)，对于 i = 0 到 4。
S 0 (0) = { (0,0), (1,0), (2,0) } = AFK
S 0 (1) = { (0,1), (1,1), (2,1) } = BGL
S 0 (2) = { (0,2), (1,2), (2,2) } = CHM
S 0 (3) = { (0,3), (1,3), (2,3) } = DIN
S 0 (4) = { (0,4), (1,4), (2,4) } = EJO
第 4 周将是
S 4 (i) 对于 i = 0 到 4。
S 4 (0) = { (0,0), (1, (4*1 + 0) mod 5), (2, (2*4 + 0) mod 5) }
= { (0,0), (1,4), (2,3) }
= AJN
S 4 (1) = { (0,1), (1, (4*1 + 1) mod 5), (2, (4*2 + 1) mod 5) }
= { (0,1), (1,0), (2,4) }
= BFO
S 4 (2) = { (0,2), (1, (4*1 + 2) mod 5), (2, (4*2 + 2) mod 5) }
= { (0,2), (1,1), (2,0) }
= CGK
S 4 (3) = { (0,3), (1, (4*1 + 3) mod 5), (2, (4*2 + 3) mod 5) }
= { (0,3), (1,2), (2,1) }
= DHL
S 4 (4) = { (0,4), (1, (4*1 + 4) mod 5), (2, (4*2 + 4) mod 5) }
= { (0,4), (1,3), (2,2) }
= EIM
以下是所有 5 周的时间表：
周：0
S 0 (0) ={(0,0) (1,0) (2,0) } = AFK
S 0 (1) ={(0,1) (1,1) (2,1) } = BGL
S 0 (2) ={(0,2) (1,2) (2,2) } = CHM
S 0 (3) ={(0,3) (1,3) (2,3) } = DIN
S 0 (4) ={(0,4) (1,4) (2,4) } = EJO
周：1
S 1 (0) ={(0,0) (1,1) (2,2) } = 股东周年大会
S 1 (1) ={(0,1) (1,2) (2,3) } = BHN
S 1 (2) ={(0,2) (1,3) (2,4) } = 首席信息官
S 1 (3) ={(0,3) (1,4) (2,0) } = DJK
S 1 (4) ={(0,4) (1,0) (2,1) } = EFL
周：2
S 2 (0) ={(0,0) (1,2) (2,4) } = AHO
S 2 (1) ={(0,1) (1,3) (2,0) } = BIK
S 2 (2) ={(0,2) (1,4) (2,1) } = CJL
S 2 (3) ={(0,3) (1,0) (2,2) } = DFM
S 2 (4) ={(0,4) (1,1) (2,3) } = EGN
周：3
S 3 (0) ={(0,0) (1,3) (2,1) } = AIL
S 3 (1) ={(0,1) (1,4) (2,2) } = BJM
S 3 (2) ={(0,2) (1,0) (2,3) } = CFN
S 3 (3) ={(0,3) (1,1) (2,4) } = DGO
S 3 (4) ={(0,4) (1,2) (2,0) } = EHK
周：4
S 4 (0) ={(0,0) (1,4) (2,3) } = AJN
S 4 (1) ={(0,1) (1,0) (2,4) } = BFO
S 4 (2) ={(0,2) (1,1) (2,0) } = CGK
S 4 (3) ={(0,3) (1,2) (2,1) } = DHL
S 4 (4) ={(0,4) (1,3) (2,2) } = EIM
在您的情况下，每组 n = 1000 名学生，k = 4。因此，我们选择 p 作为最大素数 <= (n/k = 1000/4 = 250)，因此 p = 241。不考虑上述“每周生成 n/k 个子集”下的更改，此方法将生成一个时间表961 名学生持续 241 周。
（可能的最大子集数的上限为 1000*999/(4*3) = 83250，尽管实际数字可能小于这个数。即便如此，此方法仍生成 58081 个子集，或大约 70%理论最大值！）
如果我们使用上面的第一种方法为正好 1000 名学生生成一个时间表，我们取 p 1 = 113，p 2 = 137（因此 p 1 + p 2 = n/k）。因此，我们可以生成 (113)^2 + (137)^2 = 31,538 个学生子集，足以持续 113 周。
如果我们使用上面的第二种方法为正好 1000 名学生生成一个时间表，我们取 p = 251。这将给我们一个 251 周的 1004 名学生的时间表；我们每周从日程表中删除 4 名幻影学生。通常，这将导致每周四组 3 人（虽然不太可能，但也可能有例如一组 2 人和两组 3 人）。 少于 4 名学生的小组的学生总数总是 4 的倍数，因此您可以手动将这些学生分成 4 人一组，但有可能稍后将其中两名学生再次聚集在另一个小组中。
这个算法的一个缺陷是它不是很灵活：如果一个学生辍学，我们将永远被一个幻影学生困住。此外，没有办法在年中将新学生添加到课程表中（除非我们通过最初创建幻影学生来允许他们）。
这个问题属于组合数学中的受限集系统的范畴。有关详细信息，请参阅本文，尤其是第 1 章和第 2 章。由于它是一个 postscript 文件，您将需要 gsview 或其他工具来查看它。
我不得不添加另一个答案，因为另一个答案已经太长了。
如果您有以下限制：
1) 你需要每周 4 人一组。
2) 某一周的每个小组是不相交的，每个学生正好属于一个小组。
3）如果两个学生在同一个小组，他们以后不能在同一个小组。
如果按如下方式构建图 G：
1）每个学生都是一个节点。
2) 如果两个学生以前没有在一个组中在一起，则他们通过一条边加入。
随着学生随意放弃/加入，这成为一个难题！即使您最初使用完整的图表，几周后，图表也可能变得非常不可预测。
你的问题：你需要找到 G 的一个跨越子图，它是 K_4 副本的并集，或者换句话说是 K_4s 的一个分区。
不幸的是，看起来这个问题是 NP-Hard：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 和 S 的 4 个元素子集的集合 C，是否存在 C 的子集 C'，使得 S 的每个元素在 C' 中恰好出现一次。
不幸的是，似乎您可能必须更改一些约束。
这是算法的一些概述。
这些可以存储在六个 n(n-1) 的数组中
现在开始尝试使用以下规则组合连续对：只有当有一个共同的字符时，才能组合两对。湾。当通过留下共同字符形成的对也可用时，组合是可能的。例如，如果我们想组合 AB 和 AC，那么我们需要检查 BC 是否也可用。C。当满足上述规则时，我们将两对组合成一个三元组（例如 AB 和 AC 合并形成 ABC），并将所有三对，例如 AB、AC 和 BC 标记为不可用。
继续这样做，在数组中寻找可用的对，并将它们合并形成三元组，并将这些对标记为不可用，直到没有可用的对或不能再形成三元组。
示例： 1. 结合 AB + AC --> ABC；标记 AB、AC 和 BC 不可用。2.结合AD + AE --> AED；标记 AD、AE 和 DE 不可用。3.结合AF + AG --> AFG；标记 AF、AG 和 FG 不可用。..
这是一种可以满足您所述要求的方法。我不知道它是否符合您的要求。
我会让你把它变成工作代码，但我不认为它应该太难并且它应该可以很好地扩展。请注意，它也应该适用于任何其他大小的子集，您可以为任何 n 平铺具有不规则 n 边形的平面，尽管这可能会变得困难。
我想到的另一种方法是：
这需要更多的簿记，并且有许多特殊情况需要处理，但再次编写代码应该不会太难。
编辑：很容易将我的第一种方法转换为更明显是图形上的算法的形式。将每个子集建模为一个节点，并将字母表中的每个字母建模为一条边。构建一个图，其中每个节点的度数为 n（子集中的元素数），每个字母（边）使用一次。
@khuss
同样的方法可以推广。但它不是线性算法，可能是指数的。
例如：当子集大小为 4 时，我们选择 2 对或更多对具有 4 个唯一字符。
例如，“AB 和 CD”或“AB、AC 和 AD”仅在满足以下条件时：
我们像以前一样继续，直到不能形成更多的 4 元组或没有更多的对可用。