1,2,3,4,5,6,7,8,9,10 10个号码7位的组合结果:
中7保5:(3组)
02 03 04 05 07 08 09
01 03 05 06 07 08 09
01 02 04 06 07 09 10中7保6:(8组)
01 02 03 06 08 09 10
01 04 05 06 08 09 10
01 03 06 07 08 09 10
01 02 06 07 08 09 10
02 03 04 05 07 08 10
02 03 04 05 06 07 08
01 02 03 04 05 07 09
02 03 04 05 06 07 10中6保6:(45组)
01 02 03 04 05 07 10
02 04 05 06 08 09 10
01 02 03 04 06 07 09
01 04 05 07 08 09 10
02 04 05 06 07 09 10
01 03 06 07 08 09 10
01 03 04 05 08 09 10
01 05 06 07 08 09 10
01 02 03 06 08 09 10
01 03 05 06 08 09 10
01 02 04 05 07 08 09
02 04 06 07 08 09 10
03 04 05 06 07 08 10
01 02 03 05 07 09 10
01 03 04 05 06 07 10
01 02 03 04 08 09 10
01 02 03 05 06 07 10
01 02 04 06 07 09 10
02 03 04 05 07 08 10
01 02 04 05 06 08 10
02 03 05 07 08 09 10
02 03 04 06 07 09 10
02 03 04 06 07 08 09
01 03 04 06 08 09 10
01 02 03 04 05 06 09
01 03 04 07 08 09 10
01 03 04 05 07 08 09
02 03 04 05 06 09 10
01 02 03 05 07 08 10
02 03 05 06 07 08 10
01 03 05 06 07 08 09
01 04 05 06 07 08 09
01 02 05 06 07 08 09
02 03 04 05 06 07 09
01 02 04 06 07 08 10
01 02 03 04 05 06 08
02 03 04 05 06 08 09
01 02 04 05 06 09 10
01 02 03 04 06 07 08
01 02 03 04 06 08 10
01 02 03 05 07 08 09
01 02 04 05 06 07 08
01 02 05 07 08 09 10
03 04 05 06 07 09 10
01 02 04 06 08 09 10哪位热心高手帮忙解决下,多谢
中7保5:(3组)
02 03 04 05 07 08 09
01 03 05 06 07 08 09
01 02 04 06 07 09 10中7保6:(8组)
01 02 03 06 08 09 10
01 04 05 06 08 09 10
01 03 06 07 08 09 10
01 02 06 07 08 09 10
02 03 04 05 07 08 10
02 03 04 05 06 07 08
01 02 03 04 05 07 09
02 03 04 05 06 07 10中6保6:(45组)
01 02 03 04 05 07 10
02 04 05 06 08 09 10
01 02 03 04 06 07 09
01 04 05 07 08 09 10
02 04 05 06 07 09 10
01 03 06 07 08 09 10
01 03 04 05 08 09 10
01 05 06 07 08 09 10
01 02 03 06 08 09 10
01 03 05 06 08 09 10
01 02 04 05 07 08 09
02 04 06 07 08 09 10
03 04 05 06 07 08 10
01 02 03 05 07 09 10
01 03 04 05 06 07 10
01 02 03 04 08 09 10
01 02 03 05 06 07 10
01 02 04 06 07 09 10
02 03 04 05 07 08 10
01 02 04 05 06 08 10
02 03 05 07 08 09 10
02 03 04 06 07 09 10
02 03 04 06 07 08 09
01 03 04 06 08 09 10
01 02 03 04 05 06 09
01 03 04 07 08 09 10
01 03 04 05 07 08 09
02 03 04 05 06 09 10
01 02 03 05 07 08 10
02 03 05 06 07 08 10
01 03 05 06 07 08 09
01 04 05 06 07 08 09
01 02 05 06 07 08 09
02 03 04 05 06 07 09
01 02 04 06 07 08 10
01 02 03 04 05 06 08
02 03 04 05 06 08 09
01 02 04 05 06 09 10
01 02 03 04 06 07 08
01 02 03 04 06 08 10
01 02 03 05 07 08 09
01 02 04 05 06 07 08
01 02 05 07 08 09 10
03 04 05 06 07 09 10
01 02 04 06 08 09 10哪位热心高手帮忙解决下,多谢
解决方案 »
- 很简单的正则表达式,替换失败,求指导
- C#监控windows窗口的打开
- 程序中使用多个线程操作数据库,为什么会经常出现Lock request time out period exceeded 的错误
- 如何确定mdi子窗体显示区域
- 访问listView子项的问题
- c#与数据库Access连接问题
- C# 怎么实现实时读取数据库里最新记录!!!
- 请问在vs.net2003中如何调试客户端脚本?
- 把数据导入到excel时如何让生成的excel在客户端??
- 新手求教!如何在C#的web应用程序中弹出一消息框?
- 如何检测鼠标按键状态(按下或抬起)
- c# winform 的dataset的datatable中如何手动添加行?
旋转矩阵涉及到的是一种组合设计:覆盖设计。而覆盖设计,填装设计,斯坦纳系,t-设计都是离散数学中组合优化问题。它们解决的是如何组合集合中的元素以达到某种特定的要求。
为了使读者更容易明白这些问题,下面先从一道相当古老的数学名题讲起。(一)寇克曼女生问题 某教员打算这样安排她班上的十五名女生散步:散步时三名女生为一组,共五组。问能否在一周内每日安排一次散步,使得每两名女生在这周内一道散步恰好一次? 看起来题目似乎很简单,然而它的彻底解决并不容易。事实上,寇克曼于1847年提出了该问题,过了100多年后,对于一般形式的寇克曼问题的存在性才彻底解决。 用1-15这15个数字分别代表这15个女生,下面给出一组符合要求的分组方法:
星期日:(1,2,3),(4,8,12),(5,10,15),(6,11,13),(7,9,14)
星期一:(1,4,5),(2,8,10),(3,13,14),(6,9,15),(7,11,12)
星期二:(1,6,7),(2,9,11),(3,12,15),(4,10,14),(5,8,13)
星期三:(1,8,9),(2,12,14),(3,5,6),(4,11,15),(7,10,13)
星期四:(1,10,11),(2,13,15),(3,4,7),(5,9,12),(6,8,14)
星期五:(1,12,13),(2,4,6),(3,9,10),(5,11,14),(7,8,15)
星期六:(1,14,15),(2,5,7),(3,8,11),(4,9,13),(6,10,12) 该问题就是最典型的组合设计问题。其本质就是如何将一个集合中的元素组合成一定的子集系以满足一定的要求。表面上看起来,寇克曼女生问题是纯粹的数学游戏,然而它的解却在医药试验设计上有很广泛的运用。 寇克曼女生问题是t-设计中很特殊的一类——可分解斯坦纳设计。下面我会详细解释这几个名词的含义。
(二)几种组合设计的含义
所谓t-设计是“策略组态,Tactical Configuration”的简称。
不妨用数学语言来定义t-设计:
S={S1,S2,……SV}是一个包含有v个元素的集合;
B1,B2,……,Bb是S的b个子集,而它们包含的元素个数和都是k个;
B={B1,B2,……Bb}是由这b个子集组成的集合(子集系),
对于固定整数t,和S的任意一个t元子集(t≥1),如果包含该子集的B中子集的个数都是同一个常数λt,则称B={B1,B2,……,Bb}是集合S上的一个t-(v,k,λt)设计,简称t-设计。
如果t-(v,k,λt)设计中,t=2,λ=1,则称为斯坦纳系(Steiner)。在该领域,我国已故的数学家陆家羲作出的巨大的贡献,如今每一本讲组合设计的书讲到这个问题,就不能不提到他的大名和以他的名字命名的定理。至今为止,斯坦纳系仍然存在着许多未解决的问题,至今还没有人证明S(17, 5,4=476)和S(18,6,5=1428)的存在或不存在。虽然它的参数显得很小。 而旋转矩阵涉及的则是另一种更加复杂、参数更多的组合设计——覆盖设计。
覆盖设计是一种经过精心设计的b个区组组成的子集系,其中每个区组都有k个元素组成。它可以确保如果选出k个元素,有m个在其中,至少有λ个区组中的元素有t个元素符合。区组中元素的顺序与区组的排列顺序不影响覆盖设计本身。
(c:v,k,t,m,λ=b)
可以用数学语言来定义比较简单的覆盖设计:
S={S1,S2,……SV)是一个包含有v个元素的集合;
B1,B2,……,Bb是S的b个子集,而它们包含的元素个数都是k个;
B={B1,B2,……Bb}是由这b个子集组成的集合(子集系)。
对于固定整数t,和S的任意一个t元子集(t≥1),如果该子集至少包含在B的λ个区组中,则称B={B1,B2,……,Bb}是集合S上的一个c-(v,k,λt)设计,简称覆盖设计。 填装设计是与覆盖设计相反的设计:
S={S1,S2,……SV)是一个包含有v个元素的集合;
B1,B2,……,Bb是S的b个子集,而它们包含的元素个数都是k个;
B={B1,B2,……Bb}是由这b个子集组成的集合(子集系)。
对于固定整数t,和S的任意一个t元子集(t≥1),如果该子集至多包含在B的λ个区组中,则称B={B1,B2,……,Bb}是集合S上的一个p- (v,k,λt)设计,简称填装设计。 t-设计又叫恰好覆盖与恰好填装。t-设计不一定存在,而覆盖设计一定存在。t-设计中,λ=1,而覆盖设计一般λ>1。此外,t-设计中m= t,所以t-设计只是覆盖设计中比较特殊的一种。 只要b足够大,显然覆盖设计一定存在。而有意义的是找到b的最小值,并找出在上最小值下的覆盖设计,此时的覆盖设计叫做最小覆盖。寻找最小覆盖的问题是组合优化问题的一类,被称为集合覆盖问题(SCP,Set covering problem),与著名的推销员旅行问题或成本最小化、利润最大化问题,都是优化问题的一种。 但是集合覆盖问题往往经这些问题更加困难。因为其它问题往往已经有比较成熟的、固定的方法。而覆盖设计并没有通用的公式,所以大部分的设计即使用如克雷般超级电脑也很难求出,全盘搜索的算法耗用时间将会是一个天文数字。 这方面,算法就显得相当重要。Oester Grad教授创造出一种全新的模拟算法,它大大提高了求解覆盖设计的速度,但它不能保证找到的覆盖设计一定是最小覆盖设计。它具有很强的通用性。而之前的其他算法往往只能解决固定某些参数的特定问题,解决的往往只是一类问题。 对覆盖设计的研究始于19世纪,1835年J?Plue Cker和W.S.B.Wool House(1844)开始研究此类问题。
到了1969年,人们发现它对军队中布阵与战略设计以及计算机芯片设计都大有用途,因此得到了迅速发展。在统计上,医药设计,农业试验,核研究,质量控制甚至在彩票中都大有用途。 组合设计问题往往来自于智力游戏,对它们的研究也是纯数学的。但是当研究逐渐深入时,人们逐渐地在生产与其他学科中发现了它的用武之地。这样对它的研究就有了更强大的动力,吸引了更多人的注意,成果也就更加丰富。 在选7的彩票涉及的旋转矩阵中,所有的(6,六)型和(5,五)型旋转矩阵都是t-设计。而一般的旋转矩阵都是覆盖设计。由于数学上对t-研究的比较多,所以有时候我们可以利用t-设计生成一些覆盖设计。 如以下的设计即为一个t-(10,3,3)设计,它在有限射影几何中有很广泛的运用。
B:(2,3,4) (1,5,10) (1,6,9)
(1,7,8) (2,9,10) (3,8,10)
(4,8,9) (4,6,7) (3,5,7) (2,5,6) 即1-10每个数字都出现了3次,而且每两个数字恰好一起出现1次。从它可以生成10注10个号(7,六)型矩阵(它相当对称,平衡但不是最优的),具体生成方法很简单,取每一组的剩余的7个数就可以生成对应的一组。
(三)组合设计的研究内容
1.存在性问题
若给出要求,研究符合要求的组合设计是否存在,以及存在的条件问题。比如,彩票中的覆盖设计问题,它的存在性就不是问题,因为只要注数足够多,总是可以覆盖的(它的上限为复式投注即完全组合,有意义的是它的下限)。而t-设计又叫恰好覆盖,它的存在性就是一个很值得研究的问题,也就是说,参数要符合什么条件,才会存在恰好覆盖一次的设计。
对存在性的研究更多的是从理论上。然而,对于一般情形的t-设计是否存在的问题,还远远没有解决。
2.构造问题
如果已知某种组合设计存在时,如何把它们构造出来?这是与实际应用联系最紧的问题。实际上,最终无论在彩票中,还是新药设计中,人们关心的是构造出的组合设计。经过数学家上百年的努力,现在已经有一些构造方法。如利用有限的射影几何,关联矩阵,数论中的差集等构造出大量的设计。用组合论自身也能解决一些构造问题。然而,对于一般情形的组合设计的构造性问题离解决还相当遥远。比如彩票中覆盖设计问题(即旋转矩阵)当参数变大时,设计的难度是几何级数上升。 对于一般的最小覆盖问题,仍然没有通用的构造方法。也就是说,目前市场上出现的许许多号码比较多的旋转矩阵,都很难保证是最小覆盖设计,也就是无法保证它是最优的。很多旋转矩阵不断地有人刷新它的下限纪录,也就是越来越接近最小覆盖设计。然而,要证明一个旋转矩阵是否已经是最小覆盖设计,是极其困难的,如果号码很少,还可以通过计算机编程用穷举的方式来解决,而号码稍微多一点,用穷举法超级电脑运算所耗用的时间也将是天文数字。 3.组合设计之间的关系
例如:一个组合设计是否与另外一个组合设计本质上一样的(同构)。比如把组合中某两个数字互换,这两个设计应该算同一种设计。每一种设计的同构设计是非常多的。有些同构是很难直接看出的,所以就需要研究同构的设计有什么特点,如何准确快速的判断和产生同构设计。 组合设计还研究如何由一个组合设计构造出另外一个。
比如旋转矩阵中存在着这样的问题,比如10个号码01-10,开始我先选定3注:
01,02,03,04,05,06,07,
01,03,05,07,08,09,10,
02,04,06,07,08,09,10
问如何添上尽可能少的注数,使它成为(7,六)型平衡式矩阵。
又如一个旋转矩阵与另外一个旋转矩阵是否同构。即使两个旋转矩阵所有参数都相同,也不一定同构。然而,在实际运用中,人们并不关心同构问题。因为只要能用就行了。
又如10个号码(7,六)型的有8注,比如是01-10这10个号码,问能否在这基础上添上尽可能少的注数,使得它成为11个号码的(7,六)型的旋转矩阵(01-11)。 4.计数问题
如果已知某类组合设计存在,自然希望知道这类设计的个数。也就是说互不同构的设计的个数。然而,这个问题是一个极其艰难的问题,现在还很少人去研究它。
比如很简单的10个号码的(7,六)型矩阵,共有多少种。号码一多,这将是一个很困难的问题。 5.最优设计
在诸多的满足要求的组合设计中,找到一个最优的设计,这是它研究的内容。比如覆盖设计很多,如何找出最小覆盖设计就是一具艰难的问题。旋转矩阵中需要用到组合优化的算法与组合构造算法。
(一)对旋转矩阵做出突出贡献的主要数学家
旋转矩阵是一个看似简单实际却异常复杂的问题,尽管有许许多多的人对它非常感兴趣,然而真正在这个领域内做出了开创性贡献的人却不是很多。要想在此领域有所作为,不仅要对组合设计的经典理论和常用方法有深入的了解,还要在此基础上有所创新。有许多国外的彩票专家,比如美国的盖尔?霍华德女士,声称旋转矩阵是由她首先提出来的。实际上,所有的旋转矩阵都是组合数学家们经过多年的精心研究得出的,而不是霍华德这样的彩票专家所能研究出来的。
在此领域内做出了突出贡献的主要组合数学家有以下几位:
1.Patric Osergard
他的主要贡献是用了全新的模拟冷却算法解决了旋转矩阵的构造问题,运用他的模拟冷却程序,可以很迅速的产生许许多多的旋转矩阵。 2.Alex Sidorenko
他研究出了许多旋转矩阵和几种产生旋转矩阵的基于图灵理论的一般方法。
3.Greg Kuperberg
他注意到线性的[v,t]编码的补集可以给出区组长度不定的覆盖设计,而这可以产生对现有的旋转矩阵的一系列改进。 4.Dan Gordon
他不仅是覆盖设计领域内多篇经典论文的合作者,而且总结了所有的旋转矩阵的成果,并且时时关注着该领域的最新进展。他收集的旋转矩阵是迄今为止最全面、最权威的。而这一切全凭他个人的兴趣,没有任何经费的支持。 以下我将对以上的数学家作一些介绍:
Dan Gordon是圣地亚哥的通讯研究中心的研究员。个人兴趣:计数理论、组合学、代数分析。
Greg Kuperberg是美国加州大学的数学系的副教授。主要研究方向是复杂性分析和微积分。他在覆盖设计的主要论文有:
(1)Asymptotically optimal covering designs(with Daniel Gordon,Oren Patashnik,and Joel Spe-ncer).J.Combin.Theory Ser.A 75(1996),page 270-280.
(2)Highly saturated packings and reduced coverings(with Gabor Fejes Toth and Wlodzimierz Kuperberg).Monats.Math.125(1998),page 127-145.
Patric Ostergard是芬兰赫尔辛基理工大学计算科学和工程系的教授。
他的兴趣集中在数学和计算机科学中系列问题。他的主要研究方向可分为以下几类:
(1)组合结构的设计
编码(覆盖编码,纠错编码等等)
组合设计
几何填装和覆盖问题
(2)局部搜索的优化
模拟冷却算法
禁忌搜索
全局优化的随机方法
(3)加密与解密
他是1996寇克曼奖的得主,这个奖是由国际组合学协会颁发的,以已故的著名组合学家寇克曼的名字来命名,用来奖励对组合学有突出贡献的数学家。除此之外,他还是组合设计杂志的编辑。
他在覆盖设计的主要贡献是彩了模拟冷却方法研究出了全新的构造覆盖设计的全新方法。
他在此领域的主要论文:
Nurmela,K.J.and Ostergard,P.R.J.“Constructing Covering Designs by Simulated Annealing”,Helsinki University of Technology Digital Systems Laboratory Series B:Technical Reports,No.10;January,1993.(二)旋转矩阵的主要算法
旋转矩阵的定义是很容易明白的,一般的业余数学爱好者理解没有任何障碍。然而,如何快速有效的构造旋转矩阵是一个数学家们一直在研究的问题。当然,这其中最关键的就是算法。而近年来最好的算法无疑是模拟冷却算法,它主要是由Patric Ostergard首创,并且得到了许多后来者的发展。
下面我简要介绍一下他论文所用的算法的主要思想。
1.Simulated Annealing模拟冷却算法
模拟冷却算法是一种随机搜索方法,它的主要特点是不用穷遍集合中每一种可能性就可以找到最优或几乎最优的状态。它是通过模拟一个分子系统的自然冷却过程来做到这一点的。在每一种状态,它随机地选择了一种相邻的状态,如这种相邻的状态有一个更低的成本,系统将会转移到该状态。如果这种相邻的状态有一个更高的成本,系统将可能会转移到该状态,也可能不会转移到该状态。转移的概率依赖现在的状态的温度参数(该值越高,转移的概率越大)和两个状态之间的成本的差异(差异越大,转移的概率越大)。温度将会渐渐低下来,最终会达到均衡。模拟冷却算法常常用来尝试发现离散数学中一些问题的几乎最优的解。 模拟算法的一般步骤如下:
(1)给定一个初始状态和初始温度
(2)外部循环
A内部循环
a随机选择一个相邻状态。若相邻状态的成本更低,转移
b若相邻状态的成本更高,转移的概率为exp{-成本差异/温度}
B降低温度
(3)返回所遇到的最优状态
模拟冷却算法的设计者需要选择以下6个参数:
初始温度和初始状态
一种状态的成本函数
一种状态的相邻函数
冷却程序
内部循环方法
外部循环方法
初始状态和初始温度实际上对算法影响不大,成本函数一般来说也比较容易定义,尤其是对覆盖设计来说,成本可以定义成重复数字的总个数。相邻函数也可以随机挑选一个向量来解决。而有效的冷却程序一般用T\'=rT,这里T指原来的温度,T\'是新的温度,r是常数,也叫冷却因子。 Patric Ostergard的关于覆盖设计的经典论文基本上就是如此定义模拟算法的参数的。 运用该算法,可以很容易算出一般的旋转矩阵。 除了模拟冷却算法之外,还有另外一些构造旋转矩阵的常用方法。
2.非连通的集合来结合覆盖设计
如果对某个v=v1+v2和所有的t1+t2=t,都有大小为N1的覆盖设计(v1,k1,t1)和大小为N2的覆盖设计(v2,k2,t2)存在,那么将有大小为N=N1*N2的覆盖设计存在。然而,可以用这种方法产生的旋转矩阵数量很少,而且构造的过程也很复杂。很少的旋转矩阵是用这种方法产生的。 3.贪婪算法
这种算法产生了许多许多的旋转矩阵,这种算法的核心思想是:每个区组都尽可能少重复前面区组的数字,一直重复下去,直到你得到一个覆盖设计。你可以用顺序、逆序或灰色、随机的顺序来重复这个过程。或者可以用你所喜欢的其它顺序。事实上,笔者起初的时候正是用这个方法来产生一些比较简单的矩阵,但是这种算法看起来容易,实际上却十分繁琐,如果不用计算机,即使是很简单的矩阵,也要耗费无数的精力。而且,这种算法只能保证可以产生旋转矩阵,却无法保证产生的旋转矩阵一定是最优的。当参数很大时,用它产生的矩阵离最优的矩阵还差的很远。 但是,可以用这种方法产生旋转矩阵,然后利用其他的优化算法对它再进一步优化,这样可以产生比较优良的旋转矩阵。 4.诱致算法
Greg Kuperberg是这种算法的主要创立者和提倡者。
先利用一个巨大的参数为(V,K,t)的旋转矩阵,从V个点中按照某种顺序或完全随机的选出v个点,然后将用他们原来的长度为K的区组隔断,得到了每个区组个数不定的一个覆盖。最后,将这个覆盖进行如下的修补即可:对每一个长度为1的区组,将该区组替换成一个(1,k,t)的覆盖设计。这是一种比较复杂的算法,然而,却是迄今最好的算法之一。 运用它可以产生优化程度比较高的矩阵。然而,运用这种算法的一个很大的限制是,必须要有一个参数很大的旋转矩阵和许许多多的参数比它小的矩阵。 这样的条件比较苛刻,所以它的运用不是十分广泛。
http://d.download.csdn.net/source/773897
里边包含:
1 线性代数方程组求解
2 内插法和外推法
3 函数数值积分
4 函数求值
5 特殊函数
6 随机数
7 排序
8 求根和非线性方程组
9 函数极值
10 特征系统
11 FFT
12 傅立叶谱的应用(含小波)
13 数据的统计分析
14 最小二乘法
15 常微分方程组
16 两点边界问题
17 积分方程与反演理论
18 偏微分方程
19 少数的数值算法
希望能找到解决方案
ArrayList al=new ArrayList(); //出k个全部组合
ArrayList aShot = new ArrayList(); ///出t个全部组合
ArrayList aSelect = new ArrayList(); ///选中的下注
int[] dNumUsed; ///单个号码使用重复数
int[] shotCovered; //t组合被覆盖的次数
private bool isSameValue(int[] a, int[] b) ///比较两个数组是否值相等
{
if(a.Length!=b.Length) return(false);
for (int i = 0; i < a.Length; i++)
{
if(a[i]!=b[i]) return(false);
}
return(true);
}
private int FindIndex(int[] a, ArrayList al) ///在数组列表中查找数组的位置,没找到返回-1
{
for (int i = 0; i < al.Count; i++)
{
int[] b = (int[])al[i];
if(isSameValue(a,b)) return(i);
}
return(-1);
}
private int CountUncoverd() //查找计算未被覆盖的数目
{
int c = 0;
foreach (int sc in shotCovered)
{
if (sc == 0) c++;
}
return (c);
}
private void btnCalNormal_Click(object sender, EventArgs e)
{
int v = (int)nudSel.Value;
int k = (int)nudShot.Value;
int t = (int)nudHas.Value;
if (v <= k || k <= t)
{
MessageBox.Show("必须选>中>保");
return;
}
al = PlaComb.C_Swap(v, k);
aShot = PlaComb.C_Swap(v, t);
dNumUsed = new int[v];
for (int i = 0; i < v; i++) dNumUsed[i]=0; ///初始化每个数字使用情况,都为0
shotCovered=new int[aShot.Count];
for (int i = 0; i < aShot.Count; i++) shotCovered[i] = 0; ///初始化每个目标被覆盖的情况,都为0
aSelect.Clear();
while (CountUncoverd()>0) ///如果被覆盖的数目不是全部,就继续选择
{
int uci;
///找到第一个未被覆盖的
for (uci = 0; uci < aShot.Count; uci++)
{
if (shotCovered[uci]==0) break;
}
///选中第一个未被覆盖的t组合
///把他补充成k组合,剩余k-t个数从使用次数最少的选取
List<int> nsel = ((int[])aShot[uci]).ToList<int>();
//单个数按使用次数从小到大返回
int[] numindex = OrderIndexOfValue(dNumUsed);
foreach (int i in numindex)
{
if (nsel.IndexOf(i) < 0) { //如果没有在新组合中,就添加
nsel.Add(i);
//dNumUsed[i]++;
}
//组合数达到k,补充完毕
if (nsel.Count >= k) break;
}
///下面补充被覆盖的情况,从新组合中产生新覆盖对象
int[] newselect=nsel.ToArray();
Array.Sort(newselect);
//添加新选择,并增加单个数字的使用次数,和目标组合的被覆盖次数
aSelect.Add(newselect);
foreach(int num in newselect) dNumUsed[num]++;
ArrayList newcover = PlaComb.C_Swap(newselect, t);
foreach (int[] cv in newcover)
{
Array.Sort(cv);
int ind = FindIndex(cv,aShot);
shotCovered[ind]++;
}
}
MessageBox.Show(string.Format("一共有{0}个优化组合",aSelect.Count));
dgvCombs.Rows.Clear();
for (int i = 0; i < aSelect.Count; i++)
{
int[] a = aSelect[i] as int[];
dgvCombs.Rows.Add();
int index = dgvCombs.Rows.Count - 1;
dgvCombs.Rows[index].HeaderCell.Value = dgvCombs.Rows.Count.ToString();
for (int j = 0; j < a.Length; j++)
{
dgvCombs[j, index].Value = a[j];
}
}
}
private void btnCalNormal_Click(object sender, EventArgs e)
{
int v = (int)nudSel.Value;
int k = (int)nudShot.Value;
int t = (int)nudHas.Value;
if (v <= k || k <= t)
{
MessageBox.Show("必须选>中>保");
return;
}
al = PlaComb.C_Swap(v, k);
dNumUsed = new int[v];
for (int i = 0; i < v; i++) dNumUsed[i]=0; ///初始化每个数字使用情况,都为0
shotCovered=new int[al.Count];
for (int i = 0; i < al.Count; i++) shotCovered[i] = 0; ///初始化每个目标被覆盖的情况,都为0
aSelect.Clear();
Random rd = new Random();
while (CountUncoverd()>0) ///如果被覆盖的数目不是全部,就继续选择
{
//单个数按使用次数从小到大返回
int[] newselect = new int[k];
int[] tmp;
//根据号码使用最少情况和被覆盖情况生成新选择
if (rbTanxin.Checked)
{
for (int i = 0; i < al.Count; i++)
{
tmp = (int[])al[i];
int[] numindex = OrderIndexOfValue(dNumUsed);
for (int j = 0; j < k; j++)
{
newselect[j] = numindex[tmp[j]];
}
Array.Sort(newselect);
int ind = FindIndex(newselect, al);
if (shotCovered[ind] <= 0) break;
}
}
else if (rbShunxu.Checked)
{
for (int i = 0; i < al.Count; i++)
{
if (shotCovered[i] > 0) continue;
tmp = (int[])al[i];
for (int j = 0; j < k; j++)
{
newselect[j] = tmp[j];
}
break;
}
}
else //随机型
{
List<int> ucv = new List<int>();
for (int i = 0; i < al.Count; i++)
{
if (shotCovered[i] == 0) ucv.Add(i);
}
int ind = rd.Next(ucv.Count);
ind = ucv.ToArray()[ind];
tmp = (int[])al[ind];
for (int j = 0; j < k; j++)
{
newselect[j] = tmp[j];
}
}
///增加单个号码使用次数
foreach (int num in newselect) dNumUsed[num]++;
//把被覆盖的节点计数加一,相同数不小于t的
for (int i = 0; i < al.Count; i++)
{
if (MeetCount(newselect, (int[])al[i]) >= t) shotCovered[i]++;
}
//添加选择
aSelect.Add(newselect);
}
MessageBox.Show(string.Format("一共有{0}个优化组合",aSelect.Count));
dgvCombs.Rows.Clear();
for (int i = 0; i < aSelect.Count; i++)
{
int[] a = aSelect[i] as int[];
dgvCombs.Rows.Add();
int index = dgvCombs.Rows.Count - 1;
dgvCombs.Rows[index].HeaderCell.Value = dgvCombs.Rows.Count.ToString();
for (int j = 0; j < a.Length; j++)
{
dgvCombs[j, index].Value = a[j];
}
}
}