有1~20共20个数字,每三个不同的数字组合一次总共可以组合1140次;但现在不能一次性选20个数字进行组合,仅可选4、5、6、7或8个数字进行三个不同数字的组合,如何才能组合出那不同的1140次组合且选用数字的次数最少(组合后的组合数字都出现全部重复也可以)
不考虑优化组数,而单独优化每个3元集的平均被覆盖次数或总组合数都是平凡的。因为不难建立一个所有1140个3元组到所有4元组的映射,每个3元组对应到一个覆盖它的4元组。这样用不多于1140个4元组就可以产生所有3元组组合,并且每个3元组只被产生1次。 事实上也可建立3-8映射,所需8元组个数更少,且每个3元组仍只被覆盖1次。
20 = 4 + 4 + 4 + 4 + 4 分成5个长4段
1) 3个数都在某个段,则取该段4个数组合。 共C(5,1)*C(4,3) = 20个组合。
2) 3个数在某两个段中,则取两段8个数组合。共C(5,2)*C(8,3) = 560个组合。(其中C(5,2...全部
不考虑优化组数,而单独优化每个3元集的平均被覆盖次数或总组合数都是平凡的。因为不难建立一个所有1140个3元组到所有4元组的映射,每个3元组对应到一个覆盖它的4元组。这样用不多于1140个4元组就可以产生所有3元组组合,并且每个3元组只被产生1次。
事实上也可建立3-8映射,所需8元组个数更少,且每个3元组仍只被覆盖1次。
20 = 4 + 4 + 4 + 4 + 4 分成5个长4段
1) 3个数都在某个段,则取该段4个数组合。
共C(5,1)*C(4,3) = 20个组合。
2) 3个数在某两个段中,则取两段8个数组合。共C(5,2)*C(8,3) = 560个组合。(其中C(5,2)*C(4,3)*2 个组合重复上面3个数在某个段的组合。
)
3) 3个数在某三个段中,则将每段分成长2小段,比如(1,2),(3,4); (5,6),(7,8); 。。。 (17,18),(19,20); 任选三段每段任取一个小段组成6个数,比如(1,2,7,8,17,18);任取其中3个数组合。
共C(5,3)*2^3*C(6,3) = 1600个组合。 但易见其中已包括了2)中除去1)中的组合,共重复10*8*6 = 480 次,1600 - 480 + 20 = 1140 与总组合次数相符。
这样只须用1)和3)来产生组合,总共需 1600 + 20 = 1620个组合。选用数组次数为 C(5,1) + C(5,3)*2^3 = 85次。
尚未严格证明其最优。背景是20元集的所有3元子集被一系列3元子集簇覆盖,(这里即所有4,5,6,7,8元子集形成的3元子集簇),求最少个3元子集簇覆盖所有3元子集,这里即85个。
若是需总组合数最少,则是要求所需子集簇不计并集重复时3元子集总个数最少,这里是1620个。收起