java基础（遍历m取n的所有组合(转)） java基础：遍历m取n的所有组合

java基础：遍历m取n的所有组合(转)[@more@]/**
*

* 求m取n的所有组合。
* m个数分别为0,1,2...m-1.
* 算法简述：
*二个组合，若仅有元素顺序不同，视其为同一个组合。
*左位系低位，右位系高位。
*按自然的取法取第一个组合(各数位分别是:0,1,2...n-1)，以后的所有组合都经上一个组合变化而来:
*从右至左，找到有增量空间的位,将其加1,使高于该位的所有位，均比其左邻位大1，从而形成新的组合。
*若所有位均无增量空间，说明所有组合均已被遍历。
*使用该方法所生成的组合数中：对任意组合int[] c,下标小的数必定小于下标大的数.
*

*/
public class Combination {
int n, m;
int[] pre; //previous combination.
public Combination(int n, int m) {
this.n = n;
this.m = m;
}
/**
* 取下一个组合。可避免一次性返回所有的组合(数量巨大，浪费资源)。
* if return null,所有组合均已取完。
*/
public int[] next() {
if (pre == null) {//取第一个组合，以后的所有组合都经上一个组合变化而来。
pre = new int[n];
for (int i = 0; i < pre.length; i++) {
pre = i;
}
int[] ret = new int[n];
System.arraycopy(pre, 0, ret, 0, n);
return ret;
}
int ni = n - 1, maxNi = m - 1;
while (pre[ni] + 1 > maxNi) {//从右至左，找到有增量空间的位。
ni--;
maxNi--;
if (ni < 0)
return null; //若未找到，说明了所有的组合均已取完。
}
pre[ni]++;
while (++ni < n) {
pre[ni] = pre[ni - 1] + 1;
}
int[] ret = new int[n];
System.arraycopy(pre, 0, ret, 0, n);
return ret;
}
} 【java基础（遍历m取n的所有组合(转)）】
来自 “ ITPUB博客 ” ，链接：http://blog.itpub.net/10617731/viewspace-963578/，如需转载，请注明出处，否则将追究法律责任。
转载于:http://blog.itpub.net/10617731/viewspace-963578/