问题描述
题目原型大概如下：
学校要评优秀学生，有十个平时都很优秀的学生，他们之间不相上下，但是评选的名额有限，假设学生人数是n(0<n<=10),评选的名额数时m(0<m<=n),那么希望随机从n名学生中选出m个学生，并且按字典序的列出所有可能的获得优秀的学生名额。n个学生的序号时从 1....n.
示例
输入：
5 2
输出：
54
53
52
51
43
42
41
32
31
21
思路
假设n个学生的序号是[1,2,...,n]，从中选m个学生，我们生成一个长度为m的数组，记录选学生的序号索引，例如n=5,m=2,那么index=[0,1]是一开始的选择学生的索引，index=[n-m,n-m+1]=[3,4]是最后一种情况，这里说明一下如何通过index数组求出编号，因为开始我们是从最小索引开始，那么用n-index[i] (0<=i<m)就是对应的学生编号，而且恰好能按照字典序由大到小的计算得到学生序号。
关键是在于index数组从开始态到啊结束态的不断变化，其实细心点可以发现，我们每移动一次（相当于+1）index末尾元素就可以得到一种选择的情况，而当最后一个元素加一后，其值超过它自己对应的最右位置时，我们就需要从最右开始找到与最右元素连续的索引位置，让这部分元素的索引从左边未移动过的最右那个元素的下一个位置开始标记自己的索引，而那个左边未移动过的最右那个元素的索引也开始移动一位，以此往复，知道所有元素的索引位置都到达了自己能到达的最终位置，结束。
示例：
假设 n = 6,m=3;end=[3,4,5]对应m=3个学生移动的最终索引位置，index=[0,1,2];这是最开始的m=3个学生的索引位置。
start:
index : 0,1,2
stuno: 1,2,3,4,5,6
index末尾元素到达自己所能到达的最后位置（+1后超出）
index : 0,1, 5
stuno: 1,2,3,4,5,6
下一步的索引变化
index : 0, 2,3
stuno: 1,2,3,4,5,6
再比如
index : 0, 4,5
stuno: 1,2,3,4,5,6
下一步将是
index : 1,2,3
stuno: 1,2,3,4,5,6
最后将是
index : 3,4,5
stuno: 1,2,3,4,5,6
代码
//注意end index中保存的索引时相对于n来说的范围时[0,1,...,n-2,n-1]
public void getAllCase(int n,int m){
if(n<=0 || m<=0 || m>n)
return;
int end[] = new int[m]; //选中的m学生对应的末尾索引
int index[] = new int[m];//当前选中的m个学生的索引值
//初始化end 和 index
for (int i = 0; i < m; i++) {
end[i] = n - m + i;//计算第i个选中的学生能到达的末尾索引
index[i] = i;
}
int l = m - 1;//第m个学生（最后一个学生）对应于m的索引
while (true) {
print(index, n, m);
index[l]++; //每次都是第m个学生的索引值加一（最后一个）
if (index[l] > end[l]) { //超过他自己本来只能到达的最大索引，说明需要进行下一轮
int t = l;
//找到l位置之前已经达到末尾位置的第一个没有到达对应末尾位置的的下标
while (t >= 0 && index[t] >= end[t]) {
t--;
}
//如果t大于等0说明上面while循环要找到的位置时存在的
if (t >= 0) {
int s = index[t];//上一步找到的第一个没有到达对应末尾位置的元素（从右往左）对应于n的索引值。
//从t到m-1除的元素索引加一（相当于后移一位，依次排列在t之后，注意：第一次的t位置就已经开始加一）
while (t < m) {
index[t++] = ++s;
}
} else {//否则说明说明位置都已经到达末尾，既是所有情况都已经遍历了一次
break;
}
}
}
}
//根据当前的索引数组答应选中的学生序号，因为索引数组时从0开始的，那么n-index[i]恰好得到对应的序号
private void print(int index[], int n, int m) {
for (int i = 0; i < m; i++) {
System.out.print(n - index[i]);
}
System.out.println();
}
网友评论