38-字符串的排列

daipeng大约 4 分钟

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

全排列是组合数学中的很重要的知识，很多问题的解决都有赖于组合排列。

全排列可以有两种解法。

递归解法

递归的解法很好解释，代码也很简短，但不好理解。和《盗梦空间》里的多层嵌套梦境类似，递归计算时是一层一层的，计算时需要从最高层往最底层逐层推进，但合并结果时往往需要从最底层往最高层逐层合并，往往我的内心是崩溃和拒绝的，这都是什么乱七八糟的玩意！

不过仔细研究透了一个递归解法后，会被递归的简洁和美所震撼，大道至简啊大兄弟！

递归解法说起来很简单，固定第一个字母，然后对剩余字母进行全排列，这样会得到所以以第一个字母为首字母的全排列。然后将第一个字母和第二个字母交换，这样以第二个字母为首字母，对剩余字母进行全排列，这样会得到以第二个字母为首字母的全排列，然后依次这般这般....

我们来看看代码。

   private  ArrayList<String> result = new ArrayList<>(); 
// a b c
    public ArrayList<String> Permutation(String str) {
        if (str == null || str.isEmpty()) {
            return result;
        }
        char[] chs = str.toCharArray();
        permutation(chs, 0);
        return result;
    }
    private void permutation(char[] chs, int start) {
        if (start >= chs.length ) {
            result.add(String.valueOf(chs));
        }
        for (int i = start; i < chs.length; i++) {
            //将第一个字符(start)与第i个交换，
            Utils.swap(chs,start,i);
            permutation(chs, start+1);
            //将第一个字符(start)与第i个再交换回来 否则会错乱
            Utils.swap(chs, i, start);
        }
    }

是不是很简洁？

字典序解法

字典序的解法理解上会简单些。

同位数的字符串的先后是指从左到右依次比较对应位上字符的先后。

比如 a b c < b a c。

对于一个字符串，我们可以依次找到下一个字符串，下下一个字符串...... 一直到最大的字符串。

下一个串是指刚刚好大于当前的串。

比如给定

1 2 5 4 3

如何找到下一个串呢？

对于一个字符串，顺位排列是最小的，逆序排列是最大的。比如 1 2 3 是最小的，3 2 1是最大的。

因为低位的权重小，所以我们先从低位看起，5 4 3 是[3 4 5]这三个数字排列的最大值，所以要得到下一个串，需要往高位找一位，我们找到2,2需要和5 4 3里的最小的3换个位置，这样我们得到了 1 3 5 4 2，然后我们需要将5 4 2变成最小的，也就是顺位 2 4 5。

好了，这样我们就得到了1 2 5 4 3的下一个串了。

我们总结下:

找到分割点，这个点是指从右到左遍历时，第一个大于它左边的元素。比如 1 2 3 4 5,第一个大于左边的就是5。有些博客上写的是逆序区。
将分割点左一个元素p和分割点右侧的刚好大于p的元素进行交换
将分割点以及其右边的元素排序为顺序。

举例来说。

1 2 3 4 5

从右向左遍历，5>4 分割点为5
将分割点左侧的第一个元素4与分割点及其右侧的元素中刚好大于4的元素交换，1 2 3 5 4
将分割点及其右侧元素排成顺序 1 2 3 5 4

1 2 5 4 3

分割点为 5
将2 与 5 4 3中刚好大于2的元素3交换 1 3 5 4 2
将 5 4 2顺序排列 2 4 5

过程知道了，代码就很简单了。三段论就可以了。

public ArrayList<String> Permutation2(String str) {
        if (str == null || str.isEmpty()) {
            return result1;
        }
        char[] chs = str.toCharArray();
        int border;
        result1.add(String.valueOf(chs));
        while ((border = findBorder(chs)) != -1) {
            int exchangePoint = findExchangeElement(chs, border - 1);
            swap(chs, exchangePoint, border - 1);
            swap(chs, border);
            result1.add(String.valueOf(chs));
        }
        return result1;

    }
	//将分割点及其右侧元素排成顺序 因为其已经是逆序的了所以两两交换即可。
    private void swap(char[] chs, int border) {
        int hi = chs.length - 1;
        while (border <= hi) {
            swap(chs, border++, hi--);
        }

    }
	//找到交换元素位置 即第一个刚好大于分割点左一元素的元素
    private int findExchangeElement(char[] chs, int p) {
        int hi = chs.length - 1;
        for (int i = hi; i > 0; i--) {
            if (chs[p] < chs[i]) {
                return i;
            }
        }
        return -1;
    }
	//找到分割点 	
    private int findBorder(char[] chs) {
        int hi = chs.length - 1;
        for (int i = hi; i > 0; i--) {
            //从右往左 第一个chs[i] > chs[i-1]的元素
            if (chs[i] > chs[i - 1]) {
                return i;
            }
        }
        return -1;
    }
 	public static void swap(char[] arr, int i, int j){
        char tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

38-字符串的排列

# 递归解法

# 字典序解法

递归解法

字典序解法