JAVA实现36选7（二） - 黑马程序员技术交流社区

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)+"毫秒";
}
}

复制代码