java使用移位法实现组合算法，java移位组合算法,组合问题在一些场景中会用

java使用移位法实现组合算法，java移位组合算法,组合问题在一些场景中会用

组合问题在一些场景中会用的到，比如火车票有很多站，就需要知道这些站之间有多少种组合，组合问题使用移位法很容易实现，移位法的移位过程说明如下：

思路是开一个数组，其下标表示1到m个数，数组元素的值为1表示其下标

代表的数被选中，为0则没选中。

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

然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为“01”组合，同时将其左边的所有“1”全部移动到数组的最左端（只有第一位变为0才需要移动，否则其左边的1本来就在最左端，无需移动）。

当第一个“1”移动到数组的m-n的位置，即n个“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

java代码和注释实现如下：

package cn.outofmemory;public class Combine {    public static void main(String[] args) {        int[] array = new int[] { 1, 2, 3, 4, 5 };        int m = array.length;        int n = 3;        // 初始化移位法需要的数组        byte[] bits = new byte[m];        for (int i = 0; i < bits.length; i++) {            bits[i] = i < n ? (byte) 1 : (byte) 0;        }        boolean find = false;        do {            // 找到10，换成01            printCombination(array, bits);            find = false;            for (int i = 0; i < m - 1; i++) {                if (bits[i] == 1 && bits[i+1] == 0) {                    find = true;                    bits[i] = 0;                    bits[i+1] = 1;                    if(bits[0] == 0)  //如果第一位为0，则将第i位置之前的1移到最左边，如为1则第i位置之前的1就在最左边，无需移动                      {                          for (int k=0, j=0; k < i; k++)   //O(n)复杂度使1在前0在后                          {                              if(bits[k] == 1)                              {                                  byte temp = bits[k];                                bits[k] = bits[j];                                bits[j] =  temp;                                j++;                              }                          }                      }                      break;                }            }        } while (find);    }    private static void printCombination(int[] array, byte[] bits) {        for (int i = 0; i < bits.length; i++) {            if (bits[i] == (byte) 1) {                System.out.print(" " + array[i] + " ");            }        }        System.out.println(";");    }}