- package my.lottery.groups;
- import java.text.SimpleDateFormat;
- import java.util.ArrayList;
- import java.util.Date;
- /***************************
- *
- * 这个类的代码虽然有100多行,但其实真在实现组合的代码就几行.
- * 而且每次获取的是一个组合,方便对组合数据的后续操作.
- *
- * 组合指:集合A中有n个元素,从n个元素中取m个,无排序的组成一组。其中任意一组叫做从n个元素中取m个的一个组合。
- * 例如:像彩票36选7。但是36选7还有一个特别号.所以36选7的组合总数应该是:
- * C(36,7)*P(6,1) = 36*35*34*33*32*31*30/7/6/5/4/3/2/1*6 = 50086080
- * System.out.println((36L*35*34*33*32*31*30)/(7*6*5*4*3*2*1)*6);
- *
- * 这里使用字典排序生成组合,字典排序就是后一个组合比前一个组合大,以6选3为例,可以产生20个组合:
- * {1,2,3} < {1,2,4} < {1,2,5} < {1,2,6} < {1,3,4} < {1,3,5} ... < {4,5,6}
- *
- * 一个组合要有以下成员:
- * 1.要进行组合的集合coll......如{1,2,3,4,5,6}
- * 2.集合A的元素个数n.........这里n=6
- * 3.取m个元素生成的组合group...如{1,2,3}
- * 4.每个组合的长度m..........这里m=3
- * 5.能产生的组合总数count.....公式C(n,m) = P(n,m)/m! count = 6*5*4/3/2/1 = 20
- * 6.最小的组合start.........集合的前m位{1,2,3}...最小组合也是字典排序的开始位置
- * 7.最大的组合end...........集合的后m位{4,5,6}...最大组合也是字典排序的结束位置
- * 8.程序如果要枚举出所有的组合要多少时间runTime
- * 因为有时候集合是无序的,所以组合所操作的应该是集合的角标,然后再根据角标得到相应的元素。
- * 如对集合{a,t,v,d,f}进行组合我们可以看成对{0,1,2,3,4}进行组合
- *
- *********************/
- public class Groups<T> {
- private T[] coll;
- private int n;
- private int m;
- private int last; // 组合的最后一个角标
- private int[] start;
- private int[] end;
-
- private static final String SEPARATOR = System.getProperty("line.separator");
- private boolean isStart = true; // 开始标记,一旦开始isStart变成flase
- private boolean isEnd = true; // 结束标记,一旦结束isEnd变成flase
- public int govCount; // 公式计算的结果
-
- public int mycount = 0; // 程序生成的结果,if(count==rightCount)表示程序的算法正确
-
- private Date statrTime; // 只是为了练习Date类
- private Date endTime;
- private String info;
- /**
- * 构造函数,初始化对象.
- * @param coll 要组合的集合如:{1,2,3,4,5,6...36}
- * @param m 要从集合中取几个元素进行组合,36选7。m=7
- */
- public Groups(T[] coll, int m) {
- this.coll = coll;
- n = coll.length;
- this.m = m;
- last = m-1;
- if (m <= 0 || m > n) throw new RuntimeException("..你小子是想干嘛..");
- }
- /**
- * 初始化最小组合{0,1,2,3,4,5,6},这里操作的是{1,2,3,4,5,6...36}的角标
- */
- private void startIndex() {
- start = new int[m];
- for (int x = 0; x < m; x++) start[x] = x;
-
- }
- /**
- * 初始化最大组合{29,30,31,32,33,34,35},这里操作的是{1,2,3,4,5,6...36}的角标
- */
- private void endIndex() {
-
- end = new int[m];
- for (int x = 0, i = n - m; x < m; x++, i++) end[x] = i;
- }
- /**
- * @return 如果没有下一个组合返回false
- */
- public boolean hasNext() {
- return isEnd;
- }
- /*************************
- *
- * 组合字典排序的算法:
- * 以 coll = {1,2,3...36} 选 7 为例.
- * 虽然1-36是有序的但是考虑到更多无序的情况我们使用角标进行组合
- * 也就是对{0,1,2...35}进行组合
- * 从最小组合 start = {0,1,2,3,4,5,6} 开始...
- * 当start的最后一个元素start[start.length-1] <= coll[coll.length-1]时...
- * start[start.length-1]++
- * 注意{0,1,2,3,4,5,6}中的0,1,2,3,4,5不变只有6在++
- * 当start的最后一个元素start[start.length-1]++到了等于coll[coll.length-1]时...
- * 最后一个元素的前一位start[start.length-1-1]+1
- * 然后前一位start[start.length-1-1]后面的 每 一个元素 = start[start.length-1-1]++.
- *
- * 和我们的十进制是一个道理的,从0开始到9,十进1.个位归零。
- * 只是不太一样的是,十进1以后.个位不是归零,而是它的前一位加1
- *
- * ...这样一直累加到最大组合{29,30,31,32,33,34,35}就求出了36选7的所有组合
- *
- * 以下是6选3的所有组合:
- * 123 124 125 126 {1,2,6} -> {1,3,4} <- {1,2+1,2+1+1}
- * 134 135 136
- * 145 146
- * 156 {1,5,6} -> {2,3,4} <- {1+1,1+1+1,1+1+1+1}
- * 234 235 236
- * 245 246
- * 256 {2,5,6} -> {3,4,5} <- {2+1,2+1+1,2+1+1+1}
- * 345 346
- * 356
- * 456
- *
- * 获取下一个组合的方法,每次获取一个组合,从最小组合开始,组合完毕时hasNext为 flase
- * @return 下一个组合的list集合
- *
- **********************************/
-
- public ArrayList<T> nextGroup() {
-
- /*只执行一次,初始化,最小组合和最大组合*/
- if (isStart) {
- statrTime = new Date(System.currentTimeMillis());
- startIndex();
- endIndex();
- isStart = false;
- mycount++;
- return index2value(start);
- }
-
- /*如果组合的最后一个角标不是集合的最后一个角标,++...*/
- if (start[last] < n - 1) {
-
- start[last] = start[last] + 1;
- mycount++;
- return index2value(start);
- }
-
- /*当组合的最后一个角标移到了集合的最后一个角标...*/
- /*从左边开始遍历start组合的每一个角标元素,也可以从右边开始,这里从左边开始比较方便*/
- for (int i = 0; i < m; i++) {
-
-
- /*和最大组合比较,如果大于,把前一个元素+1,然后前一个元素后面的每个元素++*/
- if (start[i] >= end[i]) {
-
- start[i - 1] = start[i - 1] + 1;
- for (int ii = i, j = 1; ii < m; ii++, j++) {
- start[ii] = start[i - 1] + j;
- }
- break;
- }
- }
- /*结束循环,当组合第一个元素的角标移到它的最大值时,组合完毕。*/
- if (start[0] >= n - m) {
- isEnd = false;
- endTime = new Date(System.currentTimeMillis());
- }
-
- mycount++;
- return index2value(start);
- }
- /**
- * 把start角标数组转换成它对应的值存储到list集合中
- * @param start start[]角标数组
- * @return 相应的值
- */
- public ArrayList<T> index2value(int[] start) {
- ArrayList<T> group = new ArrayList<T>();
- for (int i : start) group.add(coll[i]);
- return group;
- }
- /**
- * @return 用公式公式计算出来的标准组合总数
- */
- public int getGovCount() {
- return (int)(factorial(n, m)/factorial(m,m));
- }
- /**
- * 阶乘的方法
- */
- private long factorial(int n, int m) {
- long val = n;
- for (int i = 1; i < m ; i++) val = val * (n - i);
- return val;
- }
- /**
- * 获取运算所使用的时间,精确到秒
- */
- public String getInfo() {
-
- SimpleDateFormat sd = new SimpleDateFormat("yyy-MM-dd HH:mm:ss");
-
- long time = endTime.getTime() - statrTime.getTime();
-
- return info ="本次运算从:"+sd.format(statrTime)+"开始"+"到:"+sd.format(endTime)+"结束"+"总共使用了:"+(time)+"毫秒";
-
- }
- }
复制代码
|
|