全排列输出（递归实现）

2019 年 10 月 4 日
筆記

全排列是一种比较常用的算法。本文给出递归实现的两个方法。

一、方法一

1.1 思想

处理递归的时候，采用两个字符串变量，一个存放固定前缀，一个存放剩下的待处理的字符串。如：

@param prefix 固定前缀@param valueToProcess 待处理的字符串

固定前缀prefix的初始值为空值“”，随着递归的进行不断变化；剩下的待处理元素，会随着递归的进行不断减少。

何时输出一个结果？

当剩下的待处理的字符串只有一个元素的时候，直接输出其中一个结果。格式为：固定前缀 + 待处理的一个元素

    private void permuteRecusion(String prefix, String valueToProcess) {        int len = valueToProcess.length();        if (len == 1) {            System.out.println(prefix + valueToProcess);            return;        }        //省略其余部分    }

依次从剩下待处理字符元素中，选择一个元素（比如A）与固定前缀组成一个新的固定前缀，然后与新的不包含选中元素（比如A）的待处理字符串元素一道，继续调用递归函数。
直到剩下的待处理元素只有一个元素时，将固定前缀和该唯一待处理的元素一道输出。

举个例子，假设要输出ABC的全排列，采用上述思想，输出全排列的过程如下：

第一步：

待处理的字符串为ABC，固定前缀为空 ""

依次从ABC中选取元素，然后与前缀组成新的前缀，有如下三种情况：

A BC , B AC , C AB （注：绿色背景的为固定前缀，黄色背景的待处理的字符串元素）

第二步：

第一步中的三个结果，继续调用递归函数，以A BC 为例，

依次从BC中选取元素，然后与前缀（A）组成新的前缀，有如下两种情况：

A BC , A CB

同理，我们可以获取B AC 和C AB 的结果，与A BC 的结果一共产生六个结果，包括：

A BC , A CB B AC , B CA C AB , C BA

第三步：

第二步产生的六个结果，继续进行。因为剩下的待处理的字符串元素只有一个，所以直接输出即可。格式为固定前缀+待处理的字符串元素。也就得到ABC的全排列结果：

ABCACBBACBCACABCBA

根据上述思想，我们就能很容易地写出递归方法了，如：

/** * @author wangmengjun * */public class Permutation {      /**     * 根据指定的字符串，输入全排列     *      * @param value     *            用于全排列的指定字符串     */    public void permutation(String value) {        if (null == value || value.length() == 0) {            throw new IllegalArgumentException("value不能为空");        }        permuteRecusion("", value);    }      /**     * 递归处理     *      * @param prefix 固定前缀     * @param valueToProcess 待处理的字符串     */    private void permuteRecusion(String prefix, String valueToProcess) {        int len = valueToProcess.length();        if (len == 1) {            System.out.println(prefix + valueToProcess);            return;        }        for (int i = 0; i < len; i++) {            permuteRecusion(prefix + valueToProcess.charAt(i), valueToProcess.substring(0, i)                    + valueToProcess.substring(i + 1, len));        }    }    }

测试代码

/** * @author wangmengjun * */public class Main {      public static void main(String[] args) {        Permutation example = new Permutation();        System.out.println("AB的全排列:");        example.permutation("AB");                System.out.println("ABC的全排列:");        example.permutation("ABC");    }  }

输出结果

AB的全排列:ABBAABC的全排列:ABCACBBACBCACABCBA

1.2 代码调整

在上述递归代码中，从待处理字符串元素中选出一个元素和固定前缀时，为了得到不包含该选中元素的新的待处理字符串元素，代码采用了字符串substring方法来做。

valueToProcess.substring(0, i)  + valueToProcess.substring(i + 1, len)

在递归中，上述substring太过频繁，不喜欢。我们写一个新的函数，效果与上述substring操作等效。代码如下：

    /**     * 返回一个不包含指定下标元素的字符串     * @param i 需要移除元素的下标     * @param valueToProcess 用于处理的字符串     * @return     */    private String populateCandidateValue(int i, String valueToProcess) {        int len = valueToProcess.length();        char[] sourceValue = valueToProcess.toCharArray();        char[] destValue = new char[len - 1];        System.arraycopy(sourceValue, 0, destValue, 0, i);        System.arraycopy(sourceValue, i + 1, destValue, i, destValue.length - i);        return new String(destValue);      }

将permuteRecusion方法中的substring代码段替换掉。

    /**     * 递归处理     *      * @param prefix 固定前缀     * @param valueToProcess 待处理的字符串     */    private void permuteRecusion(String prefix, String valueToProcess) {        int len = valueToProcess.length();        if (len == 1) {            System.out.println(prefix + valueToProcess);            return;        }        for (int i = 0; i < len; i++) {            permuteRecusion(prefix + valueToProcess.charAt(i),                    populateCandidateValue(i, valueToProcess));        }    }

将上述改动，存放在一个新的文件Permutation2.java中。

/** * @author wangmengjun * */public class Permutation2 {      /**     * 根据指定的字符串，输入全排列     *      * @param value     *            用于全排列的指定字符串     */    public void permutation(String value) {        if (null == value || value.length() == 0) {            throw new IllegalArgumentException("value不能为空");        }        permuteRecusion("", value);    }      /**     * 递归处理     *      * @param prefix 固定前缀     * @param valueToProcess 待处理的字符串     */    private void permuteRecusion(String prefix, String valueToProcess) {        int len = valueToProcess.length();        if (len == 1) {            System.out.println(prefix + valueToProcess);            return;        }        for (int i = 0; i < len; i++) {            permuteRecusion(prefix + valueToProcess.charAt(i),                    populateCandidateValue(i, valueToProcess));        }    }      /**     * 返回一个不包含指定下标元素的字符串     * @param i 需要移除元素的下标     * @param valueToProcess 用于处理的字符串     * @return     */    private String populateCandidateValue(int i, String valueToProcess) {        int len = valueToProcess.length();        char[] sourceValue = valueToProcess.toCharArray();        char[] destValue = new char[len - 1];        System.arraycopy(sourceValue, 0, destValue, 0, i);        System.arraycopy(sourceValue, i + 1, destValue, i, destValue.length - i);        return new String(destValue);      }  }

在Permutation2.java中，我们增加了一个函数，用于返回一个不包含指定下标元素的字符串。在这个方法中，我们先将源字符串转换成char数组，然后通过数组复制，返回时，又将目标char数组，转换成String来处理。 还是不喜欢，直接使用char[]数组不就可以了吗？

接下来，我们再来做一些调整，将待处理的字符串，从String改成char[]。修改后的代码如下，存放在Permutation3.java中，

/** * @author wangmengjun * */public class Permutation3 {      /**     * 根据指定的字符串，输入全排列     *      * @param value     *            用于全排列的指定字符串     */    public void permutation(String value) {        if (null == value || value.length() == 0) {            throw new IllegalArgumentException("value不能为空");        }        permuteRecusion("", value.toCharArray());    }      /**     * 递归处理     *      * @param prefix 固定前缀     * @param valueToProcess 待处理的字符串     */    private void permuteRecusion(String prefix, char[] valueToProcess) {        int len = valueToProcess.length;        if (len == 1) {            System.out.println(prefix + valueToProcess[0]);            return;        }        for (int i = 0; i < len; i++) {            permuteRecusion(prefix + valueToProcess[i], populateCandidateValue(i, valueToProcess));        }    }      /**     * 返回一个不包含指定下标元素的字符串     * @param i 需要移除元素的下标     * @param valueToProcess 用于处理的字符串     * @return     */    private char[] populateCandidateValue(int i, char[] sourceValue) {        int len = sourceValue.length;        char[] destValue = new char[len - 1];        System.arraycopy(sourceValue, 0, destValue, 0, i);        System.arraycopy(sourceValue, i + 1, destValue, i, destValue.length - i);        return destValue;      }  }

至此，方法一的实现就全部结束了。

二、方法二（采用交换的算法）

2.1 思想

方法二的思想是采用交换的算法，思想来源于GeeksforGeeks.org. 网站

ABC全排列的过程如下图所示：

根据上述思想，编写代码如下：

/** *  * @author wangmengjun * */public class Permute {      public void permute(String value) {        if (StringUtils.isEmpty(value)) {            throw new IllegalArgumentException("内容不能为空");        }          int len = value.length();        permuteRecusion(value.toCharArray(), 0, len - 1);    }      private void permuteRecusion(char[] charValues, int begin, int end) {        if (begin == end) {            System.out.println(Arrays.toString(charValues));            return;        }        for (int i = begin; i <= end; i++) {            swap(charValues, begin, i);            permuteRecusion(charValues, begin + 1, end);            swap(charValues, begin, i);        }    }      private void swap(char[] charValues, int i, int j) {        char temp = charValues[i];        charValues[i] = charValues[j];        charValues[j] = temp;    }}

三、小结

本篇博文给出了两个递归实现全排列输出的方法。其中，

方法一给出了思想，代码实现、以及对代码的部分优化，也算是一个不错的编写代码的旅程。

方法二，如大家有兴趣，可以参考上述给出的连接，查看更详细的内容。在

本篇博文中就不详细展开讲了，有思路了，编写代码就简单了。

方法二中，使用交换的思想，维持一个char数组，其他通过变换来做。相对方法一，减少了很多数组拷贝或者String对象创建等，相比方法一来讲更好。方法一的优势在于比较好理解。

注：如上两种方法适合没有重复元素的结果，如果有重复元素，还得添加额外的判断条件进行过滤。

全排列输出递归实现就写到这里，后期会找时间将非递归的实现写上去。

如大家有较好的方法，也请告诉我一下，相互交流、相互进步~~~