java如何遍歷m取n的所有組合

這篇文章將為大家詳細(xì)講解有關(guān)java如何遍歷m取n的所有組合，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

 示例：

  * 求m取n的所有組合。

  * m個(gè)數(shù)分別為0,1,2...m-1.

  * 算法簡(jiǎn)述：

  *   二個(gè)組合，若僅有元素順序不同，視其為同一個(gè)組合。

  *   左位系低位，右位系高位。

  *   按自然的取法取第一個(gè)組合(各數(shù)位分別是:0,1,2...n-1)，以后的所有組合都經(jīng)上一個(gè)組合變化而來:

  *   從右至左，找到有增量空間的位,將其加1,使高于該位的所有位，均比其左鄰位大1，從而形成新的組合。

  *   若所有位均無增量空間，說明所有組合均已被遍歷。

  *   使用該方法所生成的組合數(shù)中：對(duì)任意組合int[] c,下標(biāo)小的數(shù)必定小于下標(biāo)大的數(shù).

  *

*/
public class Combination {
int n, m;
int[] pre;//previous combination.
public Combination(int n, int m) {
this.n = n;
this.m = m;
}
/**
* 取下一個(gè)組合?？杀苊庖淮涡苑祷厮械慕M合(數(shù)量巨大，浪費(fèi)資源)。
* if return null,所有組合均已取完。
*/
public int[] next() {
if (pre == null) {//取第一個(gè)組合，以后的所有組合都經(jīng)上一個(gè)組合變化而來。
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;
}
}

關(guān)于“java如何遍歷m取n的所有組合”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。