1.概述

在高中的时候经常会遇到一些排列组合的问题，那个时候基本上都是基于公式计算的。其实理论上是可以枚举出来的，而计算机最擅长的事情就是枚举，本文主要讨论a,b,c三个字符的各种排列组合问题，当字符增加的时候，思路是相同的。

2.可重复排列

可重复排列就是给定，a,b,c三个字符，组成长度为3的字符串，其中a,b,c可以使用多次。这个时候可以使用递归思想：第一个字符从a,b,c中选择一个，之后的问题转化为：a,b,c三个字符组成长度为2的字符串。控制好递归退出的条件，即可。

public class Permutation {
    public static void main(String[] args) {
        char[] chs = {'a', 'b', 'c'};
        per(new char[3], chs, 3 - 1);
    }

    public static void per(char[] buf, char[] chs, int len) {
        if (len == -1) {
            for (int i = buf.length - 1; i >= 0; --i) {
                System.out.print(buf[i]);
            }
            System.out.println();
            return;
        }
        for (int i = 0; i < chs.length; i++) {
            buf[len] = chs[i];
            per(buf, chs, len - 1);
        }
    }
}

3.全排列

全排列的意思，就是只能用a,b,c三个元素，做排列，每个用且只能用一次。

也可以利用递归，第一个字符串一共有n种选择，剩下的变成一个n-1规模的递归问题。而第一个字符的n种选择，都是字符串里面的。因此可以使用第一个字符与1-n的位置上进行交换，得到n种情况，然后递归处理n-1的规模，只是处理完之后需要在换回来，变成原来字符的样子。

public class Permutations {
    public static void main(String[] args) {
        char[] arrs = {'a','b','c'};
        List<List<Character>> results = new Permutations().permute(arrs);
        for (List<Character> tempList : results){
            System.out.println(String.join(",",
                    tempList.stream().map(s->String.valueOf(s)).collect(Collectors.toList())));
        }
    }

    public List<List<Character>> permute(char[] nums) {
        List<List<Character>> lists = new LinkedList<>();
        tempPermute(nums, 0, lists);
        return lists;
    }

    public void tempPermute(char[] nums, int start, List<List<Character>> lists){
        int len = nums.length;
        if(start == len-1){
            List<Character> l = new LinkedList<>();
            for(char num : nums){
                l.add(num);
            }
            lists.add(l);
            return;
        }
        for(int i=start; i<len; i++){
            char temp = nums[start];
            nums[start] = nums[i];
            nums[i] = temp;
            tempPermute(nums, start+1, lists);
            temp = nums[start];
            nums[start] = nums[i];
            nums[i] = temp;
        }
    }
}

在1中使用打印的方式，这里使用返回值的方式，因为有些场景我们希望得到值并且返回。

4.组合

求所有组合也就是abc各个位是否选取的问题，第一位2中可能，第二位2种。。。所以一共有2^{n种。用0表示不取，1表示选取，这样可以用110这样的形式表示ab。abc一共的表示形式从0到2}3-1。然后按位与运算，如果结果为1就输出当前位，结果0不输出。

public class Comb {
    public static void main(String[] args) {
        char[] chs = {'a','b','c'};
        comb(chs);
    }
 
    public static void comb(char[] chs) {
        int len = chs.length;
        int nbits = 1 << len;
        for (int i = 0; i < nbits; ++i) {
            int t;
            for (int j = 0; j < len; j++) {
                t = 1 << j;
                if ((t & i) != 0) { // 与运算，同为1时才会输出
                    System.out.print(chs[j]);
                }
            }
            System.out.println();
        }
    }
}