假设您有 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 个字母的分区。
每周生成 n/k 个子集
这种方法的最大缺点是它为 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 或其他工具来查看它。