khu*_*uss 17 algorithm math combinatorics
我期待创建一种特殊类型的组合,其中没有两个集合具有多个交叉元素.让我用一个例子来解释一下:
假设我们有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.
任何帮助都非常感谢.
谢谢
小智 11
假设您有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)本身代表一个"字母分组"aka.一个大小为k的子集.
S w(i)的公式是
Sw(i) = {(0,i mod p), (1,(w+i) mod p), (2,(2w+i) mod p),..., ((k-1),((k-1)*w+i) mod p)}
= { (x,y) | 0 <= x < k and 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这样的元素
w1*x + i1 = w2*x + i2 (mod p) (w1-w2)*x + (i1-i2) = 0 (mod p)
然而,任何采用模运算的人都知道如果p是素数,则x具有唯一解或者(w 1 = w 2且i 1 = i 2); 因此,不能有多于一个x,并且S w1(i 1)和S w2(i 2)可以具有至多一个交叉元素.
因为p < n/k,通过切比雪夫的定理(其中说x和2x之间的素数为x> 3)
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变化.
考虑我们创建的组:
Sw(i) = { (x,y) | 0 <= x < k and y = w*x + i (mod p)}
假设w是固定的,i从0到p-1不等.然后我们得到p集:
Sw(0), Sw(1), ..., Sw(p-1)
现在让我们说S w(i 1)和S w(i 2)(与i 1 =/= i 2)相交; 然后
w*x + i1 = w*x + i2 (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 我ķ字母作为一个独立的字母,这样而不是寻找的对亚 ķ信件,我们发现的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周,我们生成分区为
S0(i), for i = 0 to 4.
S0(0) = { (0,0), (1,0), (2,0) } = AFK
S0(1) = { (0,1), (1,1), (2,1) } = BGL
S0(2) = { (0,2), (1,2), (2,2) } = CHM
S0(3) = { (0,3), (1,3), (2,3) } = DIN
S0(4) = { (0,4), (1,4), (2,4) } = EJO
对于第4周,它将是
S4(i) for i = 0 to 4.
S4(0) = { (0,0), (1, (4*1 + 0) mod 5), (2, (2*4 + 0) mod 5) }
= { (0,0), (1,4), (2,3) }
= AJN
S4(1) = { (0,1), (1, (4*1 + 1) mod 5), (2, (4*2 + 1) mod 5) }
= { (0,1), (1,0), (2,4) }
= BFO
S4(2) = { (0,2), (1, (4*1 + 2) mod 5), (2, (4*2 + 2) mod 5) }
= { (0,2), (1,1), (2,0) }
= CGK
S4(3) = { (0,3), (1, (4*1 + 3) mod 5), (2, (4*2 + 3) mod 5) }
= { (0,3), (1,2), (2,1) }
= DHL
S4(4) = { (0,4), (1, (4*1 + 4) mod 5), (2, (4*2 + 4) mod 5) }
= { (0,4), (1,3), (2,2) }
= EIM
这是所有5周的时间表:
Week: 0
S0(0) ={(0,0) (1,0) (2,0) } = AFK
S0(1) ={(0,1) (1,1) (2,1) } = BGL
S0(2) ={(0,2) (1,2) (2,2) } = CHM
S0(3) ={(0,3) (1,3) (2,3) } = DIN
S0(4) ={(0,4) (1,4) (2,4) } = EJO
Week: 1
S1(0) ={(0,0) (1,1) (2,2) } = AGM
S1(1) ={(0,1) (1,2) (2,3) } = BHN
S1(2) ={(0,2) (1,3) (2,4) } = CIO
S1(3) ={(0,3) (1,4) (2,0) } = DJK
S1(4) ={(0,4) (1,0) (2,1) } = EFL
Week: 2
S2(0) ={(0,0) (1,2) (2,4) } = AHO
S2(1) ={(0,1) (1,3) (2,0) } = BIK
S2(2) ={(0,2) (1,4) (2,1) } = CJL
S2(3) ={(0,3) (1,0) (2,2) } = DFM
S2(4) ={(0,4) (1,1) (2,3) } = EGN
Week: 3
S3(0) ={(0,0) (1,3) (2,1) } = AIL
S3(1) ={(0,1) (1,4) (2,2) } = BJM
S3(2) ={(0,2) (1,0) (2,3) } = CFN
S3(3) ={(0,3) (1,1) (2,4) } = DGO
S3(4) ={(0,4) (1,2) (2,0) } = EHK
Week: 4
S4(0) ={(0,0) (1,4) (2,3) } = AJN
S4(1) ={(0,1) (1,0) (2,4) } = BFO
S4(2) ={(0,2) (1,1) (2,0) } = CGK
S4(3) ={(0,3) (1,2) (2,1) } = DHL
S4(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组和2组3组). 拥有<4名学生的小组总是拥有4个学生的总数,因此您可以手动将这些学生分成4个小组,这样可能会让其中两个学生再次聚集在另一个小组中.
这个算法的一个缺陷是它不是很灵活:如果一个学生辍学,我们会永远被一个幻影学生困住.此外,没有办法将新学生添加到一年中的时间表中(除非我们通过最初创建幻影学生来允许他们).
此问题属于组合系统中的限制集系统类别.有关详细信息,请参阅此文章,尤其是第1章和第2章.由于它是postscript文件,因此您需要使用gsview或其他内容来查看它.
小智 3
我必须添加另一个答案，因为另一个答案已经太长了。
如果您有以下限制：
1) 每周需要 4 人一组。
2）某一周的每个小组都是不相交的，并且每个学生都恰好在一个小组中。
3) 如果两个学生在同一组，则他们以后不能在同一组。
如果构建一个图G如下：
1）每个学生都是一个节点。
2) 两个学生通过一条边连接在一起，前提是他们以前没有在一个小组中在一起。
随着学生任意退学/加入，这成为一个难题！即使您一开始有一个完整的图表，几周后，该图表可能会变得相当不可预测。
你的问题：你需要找到 G 的一个生成子图，这样它就是 K_4 副本的并集，或者换句话说，它是 K_4 的分区。
不幸的是，看起来这个问题是 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' 中精确出现一次。
不幸的是，似乎您可能必须更改一些限制。