字符串的排列

题目：

​ 输入一个字符串，打印出该字符串中字符 的所有排列。例如，输入字符串 abc，则打印出由字符 a、b、c 所有能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba。

分析：

​ 面对这样的题目，我们需要将复杂问题分解化，分解成一个一个小问题。将一个字符串分为两部分：第一部分为它的第一个字符，第二部分为后面所有的字符，如下图所示：

​ 求整个字符串的全排列，可以看成两步：第一步首先求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换，上图就是分别把第一个字符a和后面的b、c等字符交换的情形；第二步固定第一个字符，求后面所有字符的排列。这时候仍然把后面的字符分成两部分，后面的第一个字符，和这个字符之后的所有字符，然后把后面的第一个字符和它后面的字符交换。

​ 注：（a）把字符串分成两部分，一部分是字符串的第一个字符，另一部分是第一个字符以后的所有字符（有阴影背景的区域）。接下来我们求阴影部分的字符串的排列。（b）拿第一个字符和它后面的字符逐个交换。

代码：

public class StringPermutation {

    public static void permutation(String str) {
        //如果字符串为空，直接返回
        if (null == str || "".equals(str)) {
            return;
        }
        //否则将字符串转换为字符数组，并从字符0位置开始进行全排列
        permutation(str.toCharArray(), 0);
    }

    private static void permutation(char[] charArr, int pos) {
        if (pos == charArr.length - 1) {
            System.out.println(Arrays.toString(charArr));
        }

        for (int i = pos; i < charArr.length; i++) {
            //首部字符和它后面的字符（包括自己）进行交换
            char temp = charArr[i];
            charArr[i] = charArr[pos];
            charArr[pos] = temp;
            //递归求后面的字符的排列
            permutation(charArr, pos+1);
            //由于前面交换了一下，所以chs的内容改变了，我们要还原回来
            temp = charArr[i];
            charArr[i] = charArr[pos];
            charArr[pos] = temp;
        }
    }
}

扩展：

如果不是求字符的所有排列，而是求字符的所有组合，应该怎么解决？还是输入三个字符a、b、c，则它们的组合有a、b、c、ab、ac、bc、abc。当交换字符串中的两个字符时，虽然能得到两个不同的排列，但却是同一个组合。比如：ab和ba是不同的排列，但只算一个组合。

public class StringCombination {

    public static void combination(String str) {
        char[] chars = str.toCharArray();
        char[] subchars = new char[chars.length]; // 存储子组合数据的数组
        // 全组合问题就是所有元素(记为n)中选1个元素的组合, 加上选2个元素的组合...加上选n个元素的组合的和
        for (int i = 0; i < chars.length; ++i) {
            final int m = i + 1;
            combination(chars, chars.length, m, subchars, m);
        }

    }

    /**
     * n个元素选m个元素的组合问题的实现. 原理如下: 从后往前选取, 选定位置i后, 再在前i-1个里面选取m-1个. 如: 1, 2, 3, 4,
     * 5 中选取3个元素. 1) 选取5后, 再在前4个里面选取2个, 而前4个里面选取2个又是一个子问题, 递归即可; 2) 如果不包含5,
     * 直接选定4, 那么再在前3个里面选取2个, 而前三个里面选取2个又是一个子问题, 递归即可; 3) 如果也不包含4, 直接选取3,
     * 那么再在前2个里面选取2个, 刚好只有两个. 纵向看, 1与2与3刚好是一个for循环, 初值为5, 终值为m. 横向看,
     * 该问题为一个前i-1个中选m-1的递归.
     */
    private static void combination(char[] chars, int n, int m, char[] subchars, int subn) {
        if (m == 0) { // 出口
            for (int i = 0; i < subn; ++i) {
                System.out.print(subchars[i]);
            }
            System.out.println();
        } else {
            for (int i = n; i >= m; --i) { // 从后往前依次选定一个
                subchars[m - 1] = chars[i - 1]; // 选定一个后
                combination(chars, i - 1, m - 1, subchars, subn); // 从前i-1个里面选取m-1个进行递归
            }
        }
    }
}

参考：

​ https://blog.csdn.net/u013132035/article/details/80639439