经常会遇到一些笔试题目，通过求出数组的所有排列组合就可以轻易解答出。今天碰巧看到一个很巧妙的求法，故记录一下
例如给定一个数组[1,2,3]，那么排列组合有如下
[1]
[2]
[3]
[1,2]
[1,3]
[2,3]
[1,2,3]
那么实际上每个排列组合都可以将其对应一个数字
[1] //1 0 0
[2] //0 1 0
[3] //0 0 1
[1,2] //1 1 0
[1,3] // 1 0 1
[2,3] //0 1 1
[1,2,3] //1 1 1
当选取元素时，将其位置标记为1；
若不选取该元素，则其位置标记为0。
那么含有3个元素的数组的所有的排列集合就是001-111一共是2^3-1=7种组合
含有n个元素的数组一共有2^n-1种组合
数组最多含32个元素，此时达到32位机上限2^32-1=4,294,967,295
给定一个数组，求其所有排列组合的代码如下：
/**
*
* @param arr 给定的数组
* @return
*/
public List<int[]> getAllCombinations(int[] arr){
List<int[]> list=new ArrayList();
int len=arr.length;
int allCombinations=(1<<len)-1; //数组的所有组合数
//从1开始计算组合
for(int i=1;i<=allCombinations;i++){
int[] combinations=new int[len]; //保存该数字对应的组合
int curPosition=len-1; //当前所在位置，自后向前
int number=i;
while(number!=0){
//若最低位为1，则取该位置的元素
if((number&1)==1){
combinations[curPosition]=arr[curPosition];
}
number=number>>>1; //无符号右移去除低位
curPosition--; //记录下一位
}
list.add(combinations);
}
return list;
}
测试：
public static void main(String[] args) {
TestPower t=new TestPower();
int[] arr=new int[]{1,2,3};
List<int[]> list = t.getAllCombinations(arr);
for(int[] array:list){
System.out.println(Arrays.toString(array));
}
}
运行结果：
[0, 0, 3]
[0, 2, 0]
[0, 2, 3]
[1, 0, 0]
[1, 0, 3]
[1, 2, 0]
[1, 2, 3]