今天用到了組合算法，我就自己寫了一個，本程序的思路來自網(wǎng)絡(luò)。

本程序的思路是開一個數(shù)組，其下標(biāo)表示1到n個數(shù)，數(shù)組元素的值為1表示其下標(biāo)代表的數(shù)被選中，為0則沒選中。

1、首先初始化，將數(shù)組前m個元素置1，表示第一個組合為前m個數(shù)。

2、然后從左到右掃描數(shù)組元素值的“10”組合，找到第一個“10”組合后將其變?yōu)椤?1”組合，同時將其左邊的所有“1”全部移動到數(shù)組的最左端。

當(dāng)?shù)谝粋€“1”移動到數(shù)組的n-m的位置，即m個“1”全部移動到最右端時，就得到了最后一個組合。

例如求5中選3的組合：
1 1 1 0 0 //1,2,3
1 1 0 1 0 //1,2,4
1 0 1 1 0 //1,3,4
0 1 1 1 0 //2,3,4
1 1 0 0 1 //1,2,5
1 0 1 0 1 //1,3,5
0 1 1 0 1 //2,3,5
1 0 0 1 1 //1,4,5
0 1 0 1 1 //2,4,5
0 0 1 1 1 //3,4,5

代碼實現(xiàn)如下：

public static int[][] combination(int n, int m) {

if (n <=1 || m > n)

return null;

    int count =(int) ( (nFactorial(n))/(nFactorial(m)*nFactorial(n-m)) );

    int[][] newO =new int[count][n];

    //開一個數(shù)組，其下標(biāo)表示1到n個數(shù)，

    int[] startArray =new int[n];

    //首先初始化，將數(shù)組前m個元素置1，表示第一個組合為前m個數(shù)。

    for (int i =0; i< m; i++){

startArray[i] =1;

    }

for (int j =0; j< startArray.length; j++)

newO[0][j] = startArray[j];

    for (int i =1; i< count; i++){

startArray  =change10To01(startArray);

        for (int j =0; j< startArray.length; j++)

newO[i][j] = startArray[j];

    }

return newO;

}

//求階乘
    public static long nFactorial(int n){
        if(n==0){
            return 1;
        }
        return n*nFactorial(n-1);
    }

//使數(shù)組的 [0, n) 項的 “1” 全部移動到數(shù)組的最左端 ，數(shù)組必須由0和1組成
    public static int[] arrRank(int[] arr, int n){
        if (n<0)
            return arr;

        for (int i = 0;i< n-1; i++) {
            if(arr[i] == 0 && arr[i+1] == 1) {
                //交換i和i+1的元素
                arr[i] = arr[i] + arr[i+1];
                arr[i+1] = arr[i] - arr[i+1];
                arr[i] = arr[i] - arr[i+1];
            }
        }
        return arrRank(arr, n-1);
    }

//左到右掃描數(shù)組元素值的“10”組合，找到第一個“10”組合后將其變?yōu)椤?1”組合
    public static int[] change10To01(int[] arr ) {

        for (int i = 0; i< arr.length -1; i++){
            if(arr[i]==1 && arr[i+1]==0) {
                //交換i和i+1的元素
                arr[i] = arr[i] + arr[i+1];
                arr[i+1] = arr[i] - arr[i+1];
                arr[i] = arr[i] - arr[i+1];
                arr = arrRank(arr, i);
                break;
            }
        }
        return arr;
    }

在計算組合的總數(shù)時，以為使用了階乘，導(dǎo)致n大于20就會造成數(shù)值的溢出。
源碼地址：https://github.com/weiyang00/Algorithms_4th/blob/master/ex_1_Fundamentals/ex_2_DataAbstraction/Ex_PermutationAndCombination.java