問題描述
題目原型大概如下：
學(xué)校要評優(yōu)秀學(xué)生，有十個平時都很優(yōu)秀的學(xué)生，他們之間不相上下，但是評選的名額有限，假設(shè)學(xué)生人數(shù)是n(0<n<=10),評選的名額數(shù)時m(0<m<=n),那么希望隨機從n名學(xué)生中選出m個學(xué)生，并且按字典序的列出所有可能的獲得優(yōu)秀的學(xué)生名額。n個學(xué)生的序號時從 1....n.
示例
輸入：
5 2
輸出：
54
53
52
51
43
42
41
32
31
21
思路
假設(shè)n個學(xué)生的序號是[1,2,...,n]，從中選m個學(xué)生，我們生成一個長度為m的數(shù)組，記錄選學(xué)生的序號索引，例如n=5,m=2,那么index=[0,1]是一開始的選擇學(xué)生的索引，index=[n-m,n-m+1]=[3,4]是最后一種情況，這里說明一下如何通過index數(shù)組求出編號，因為開始我們是從最小索引開始，那么用n-index[i] (0<=i<m)就是對應(yīng)的學(xué)生編號，而且恰好能按照字典序由大到小的計算得到學(xué)生序號。
關(guān)鍵是在于index數(shù)組從開始態(tài)到啊結(jié)束態(tài)的不斷變化，其實細心點可以發(fā)現(xiàn)，我們每移動一次（相當(dāng)于+1）index末尾元素就可以得到一種選擇的情況，而當(dāng)最后一個元素加一后，其值超過它自己對應(yīng)的最右位置時，我們就需要從最右開始找到與最右元素連續(xù)的索引位置，讓這部分元素的索引從左邊未移動過的最右那個元素的下一個位置開始標(biāo)記自己的索引，而那個左邊未移動過的最右那個元素的索引也開始移動一位，以此往復(fù)，知道所有元素的索引位置都到達了自己能到達的最終位置，結(jié)束。
示例：
假設(shè) n = 6,m=3;end=[3,4,5]對應(yīng)m=3個學(xué)生移動的最終索引位置，index=[0,1,2];這是最開始的m=3個學(xué)生的索引位置。
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學(xué)生對應(yīng)的末尾索引
int index[] = new int[m];//當(dāng)前選中的m個學(xué)生的索引值
//初始化end 和 index
for (int i = 0; i < m; i++) {
end[i] = n - m + i;//計算第i個選中的學(xué)生能到達的末尾索引
index[i] = i;
}
int l = m - 1;//第m個學(xué)生（最后一個學(xué)生）對應(yīng)于m的索引
while (true) {
print(index, n, m);
index[l]++; //每次都是第m個學(xué)生的索引值加一（最后一個）
if (index[l] > end[l]) { //超過他自己本來只能到達的最大索引，說明需要進行下一輪
int t = l;
//找到l位置之前已經(jīng)達到末尾位置的第一個沒有到達對應(yīng)末尾位置的的下標(biāo)
while (t >= 0 && index[t] >= end[t]) {
t--;
}
//如果t大于等0說明上面while循環(huán)要找到的位置時存在的
if (t >= 0) {
int s = index[t];//上一步找到的第一個沒有到達對應(yīng)末尾位置的元素（從右往左）對應(yīng)于n的索引值。
//從t到m-1除的元素索引加一（相當(dāng)于后移一位，依次排列在t之后，注意：第一次的t位置就已經(jīng)開始加一）
while (t < m) {
index[t++] = ++s;
}
} else {//否則說明說明位置都已經(jīng)到達末尾，既是所有情況都已經(jīng)遍歷了一次
break;
}
}
}
}
//根據(jù)當(dāng)前的索引數(shù)組答應(yīng)選中的學(xué)生序號，因為索引數(shù)組時從0開始的，那么n-index[i]恰好得到對應(yīng)的序號
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();
}
