A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 354620815 中级黑马   /  2014-10-3 15:23  /  1752 人查看  /  2 人回复  /   1 人收藏 转载请遵从CC协议 禁止商业使用本文

  1. package my.lottery.groups;

  2. import java.text.SimpleDateFormat;
  3. import java.util.ArrayList;
  4. import java.util.Date;

  5. /***************************
  6. *
  7. * 这个类的代码虽然有100多行,但其实真在实现组合的代码就几行.
  8. * 而且每次获取的是一个组合,方便对组合数据的后续操作.
  9. *
  10. * 组合指:集合A中有n个元素,从n个元素中取m个,无排序的组成一组。其中任意一组叫做从n个元素中取m个的一个组合。
  11. * 例如:像彩票36选7。但是36选7还有一个特别号.所以36选7的组合总数应该是:
  12. * C(36,7)*P(6,1) = 36*35*34*33*32*31*30/7/6/5/4/3/2/1*6 = 50086080
  13. * System.out.println((36L*35*34*33*32*31*30)/(7*6*5*4*3*2*1)*6);
  14. *
  15. * 这里使用字典排序生成组合,字典排序就是后一个组合比前一个组合大,以6选3为例,可以产生20个组合:
  16. * {1,2,3} < {1,2,4} < {1,2,5} < {1,2,6} < {1,3,4} < {1,3,5} ... < {4,5,6}
  17. *
  18. * 一个组合要有以下成员:
  19. *                 1.要进行组合的集合coll......如{1,2,3,4,5,6}       
  20. *                 2.集合A的元素个数n.........这里n=6
  21. *                 3.取m个元素生成的组合group...如{1,2,3}
  22. *                 4.每个组合的长度m..........这里m=3       
  23. *                 5.能产生的组合总数count.....公式C(n,m) = P(n,m)/m!  count = 6*5*4/3/2/1 = 20
  24. *                 6.最小的组合start.........集合的前m位{1,2,3}...最小组合也是字典排序的开始位置       
  25. *                 7.最大的组合end...........集合的后m位{4,5,6}...最大组合也是字典排序的结束位置
  26. *                 8.程序如果要枚举出所有的组合要多少时间runTime
  27. * 因为有时候集合是无序的,所以组合所操作的应该是集合的角标,然后再根据角标得到相应的元素。
  28. * 如对集合{a,t,v,d,f}进行组合我们可以看成对{0,1,2,3,4}进行组合
  29. *
  30. *********************/
  31. public class Groups<T> {

  32.         private T[] coll;
  33.         private int n;
  34.         private int m;
  35.         private int last; // 组合的最后一个角标
  36.         private int[] start;
  37.         private int[] end;
  38.        
  39.         private static final String SEPARATOR = System.getProperty("line.separator");

  40.         private boolean isStart = true; // 开始标记,一旦开始isStart变成flase

  41.         private boolean isEnd = true; // 结束标记,一旦结束isEnd变成flase

  42.         public int govCount; // 公式计算的结果
  43.        
  44.         public int mycount = 0; // 程序生成的结果,if(count==rightCount)表示程序的算法正确
  45.        
  46.         private Date statrTime; // 只是为了练习Date类
  47.         private Date endTime;
  48.         private String info;       
  49.         /**
  50.          * 构造函数,初始化对象.
  51.          * @param coll 要组合的集合如:{1,2,3,4,5,6...36}
  52.          * @param m    要从集合中取几个元素进行组合,36选7。m=7       
  53.          */
  54.         public Groups(T[] coll, int m) {

  55.                 this.coll = coll;
  56.                 n = coll.length;
  57.                 this.m = m;
  58.                 last = m-1;
  59.                 if (m <= 0 || m > n) throw new RuntimeException("..你小子是想干嘛..");                       
  60.         }       
  61.         /**
  62.          * 初始化最小组合{0,1,2,3,4,5,6},这里操作的是{1,2,3,4,5,6...36}的角标
  63.          */
  64.         private void startIndex() {
  65.                 start = new int[m];
  66.                 for (int x = 0; x < m; x++) start[x] = x;
  67.                
  68.         }       
  69.         /**
  70.          * 初始化最大组合{29,30,31,32,33,34,35},这里操作的是{1,2,3,4,5,6...36}的角标
  71.          */
  72.         private void endIndex() {
  73.                
  74.                 end = new int[m];
  75.                 for (int x = 0, i = n - m; x < m; x++, i++) end[x] = i;               
  76.         }       
  77.         /**
  78.          * @return 如果没有下一个组合返回false
  79.          */
  80.         public boolean hasNext() {
  81.                 return isEnd;
  82.         }       
  83.         /*************************
  84.          *
  85.          * 组合字典排序的算法:
  86.          *         以 coll = {1,2,3...36} 选 7 为例.
  87.          *         虽然1-36是有序的但是考虑到更多无序的情况我们使用角标进行组合
  88.          *         也就是对{0,1,2...35}进行组合
  89.          *         从最小组合  start = {0,1,2,3,4,5,6} 开始...
  90.          *         当start的最后一个元素start[start.length-1] <= coll[coll.length-1]时...
  91.          *         start[start.length-1]++
  92.          *         注意{0,1,2,3,4,5,6}中的0,1,2,3,4,5不变只有6在++
  93.          *         当start的最后一个元素start[start.length-1]++到了等于coll[coll.length-1]时...
  94.          *         最后一个元素的前一位start[start.length-1-1]+1
  95.          *         然后前一位start[start.length-1-1]后面的   每   一个元素  = start[start.length-1-1]++.
  96.          *
  97.          *  和我们的十进制是一个道理的,从0开始到9,十进1.个位归零。
  98.          *  只是不太一样的是,十进1以后.个位不是归零,而是它的前一位加1
  99.          *  
  100.          *  ...这样一直累加到最大组合{29,30,31,32,33,34,35}就求出了36选7的所有组合
  101.          *  
  102.          *  以下是6选3的所有组合:
  103.          *  123 124 125 126                        {1,2,6} -> {1,3,4} <- {1,2+1,2+1+1}
  104.          *  134 135 136
  105.          *  145 146
  106.          *  156                                         {1,5,6} -> {2,3,4} <- {1+1,1+1+1,1+1+1+1}
  107.          *  234 235 236
  108.          *  245 246
  109.          *  256                                                {2,5,6} -> {3,4,5} <- {2+1,2+1+1,2+1+1+1}
  110.          *  345 346
  111.          *  356
  112.          *  456
  113.          *  
  114.          *         获取下一个组合的方法,每次获取一个组合,从最小组合开始,组合完毕时hasNext为 flase
  115.          *         @return 下一个组合的list集合
  116.          *
  117.          **********************************/       
  118.        
  119.         public ArrayList<T> nextGroup() {
  120.                
  121.                 /*只执行一次,初始化,最小组合和最大组合*/               
  122.                 if (isStart) {
  123.                         statrTime = new Date(System.currentTimeMillis());
  124.                         startIndex();
  125.                         endIndex();
  126.                         isStart = false;
  127.                         mycount++;
  128.                         return index2value(start);                         
  129.                 }
  130.                
  131.                 /*如果组合的最后一个角标不是集合的最后一个角标,++...*/
  132.                 if (start[last] < n - 1) {                       
  133.                        
  134.                         start[last] = start[last] + 1;                       
  135.                         mycount++;
  136.                         return index2value(start);
  137.                 }               
  138.                
  139.                 /*当组合的最后一个角标移到了集合的最后一个角标...*/               
  140.                 /*从左边开始遍历start组合的每一个角标元素,也可以从右边开始,这里从左边开始比较方便*/
  141.                 for (int i = 0; i < m; i++) {

  142.                        
  143.                        
  144.                         /*和最大组合比较,如果大于,把前一个元素+1,然后前一个元素后面的每个元素++*/
  145.                         if (start[i] >= end[i]) {                               
  146.                                
  147.                                 start[i - 1] = start[i - 1] + 1;

  148.                                 for (int ii = i, j = 1; ii < m; ii++, j++) {
  149.                                         start[ii] = start[i - 1] + j;
  150.                                 }
  151.                                 break;
  152.                         }
  153.                 }               
  154.                 /*结束循环,当组合第一个元素的角标移到它的最大值时,组合完毕。*/
  155.                 if (start[0] >= n - m) {
  156.                         isEnd = false;
  157.                         endTime = new Date(System.currentTimeMillis());
  158.                 }
  159.                
  160.                 mycount++;
  161.                 return index2value(start);               
  162.         }       
  163.         /**
  164.          * 把start角标数组转换成它对应的值存储到list集合中
  165.          * @param start         start[]角标数组
  166.          * @return                      相应的值
  167.          */               
  168.         public ArrayList<T> index2value(int[] start) {
  169.                 ArrayList<T> group = new ArrayList<T>();
  170.                 for (int i : start)        group.add(coll[i]);
  171.                 return group;
  172.         }       
  173.         /**
  174.          * @return 用公式公式计算出来的标准组合总数
  175.          */
  176.         public int getGovCount() {
  177.                 return (int)(factorial(n, m)/factorial(m,m));
  178.         }       
  179.         /**
  180.          *        阶乘的方法
  181.          */
  182.         private long factorial(int n, int m) {               
  183.                 long val = n;
  184.                 for (int i = 1; i < m ; i++) val = val * (n - i);
  185.                 return val;
  186.         }       
  187.         /**
  188.          * 获取运算所使用的时间,精确到秒
  189.          */
  190.         public String getInfo() {
  191.                
  192.                 SimpleDateFormat sd = new SimpleDateFormat("yyy-MM-dd  HH:mm:ss");
  193.                
  194.                 long time = endTime.getTime() - statrTime.getTime();
  195.                
  196.                 return info ="本次运算从:"+sd.format(statrTime)+"开始"+"到:"+sd.format(endTime)+"结束"+"总共使用了:"+(time)+"毫秒";               
  197.                
  198.         }
  199. }
复制代码


2 个回复

倒序浏览
楼主好厉害!
回复 使用道具 举报
只能伸出大拇指,
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马