组合算法

今天用到了组合算法，我就自己写了一个，本程序的思路来自网络。

本程序的思路是开一个数组，其下标表示1到n个数，数组元素的值为1表示其下标代表的数被选中，为0则没选中。

1、首先初始化，将数组前m个元素置1，表示第一个组合为前m个数。

2、然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。

当第一个“1”移动到数组的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

代码实现如下：

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];

    //开一个数组，其下标表示1到n个数，

    int[] startArray =new int[n];

    //首先初始化，将数组前m个元素置1，表示第一个组合为前m个数。

    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);
    }

//使数组的 [0, n) 项的 “1” 全部移动到数组的最左端 ，数组必须由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);
    }

//左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为“01”组合
    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;
    }

在计算组合的总数时，以为使用了阶乘，导致n大于20就会造成数值的溢出。
源码地址：https://github.com/weiyang00/Algorithms_4th/blob/master/ex_1_Fundamentals/ex_2_DataAbstraction/Ex_PermutationAndCombination.java