前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >全排列输出(递归实现)

全排列输出(递归实现)

作者头像
孟君
发布2019-09-17 10:48:35
1.4K0
发布2019-09-17 10:48:35
举报
文章被收录于专栏:孟君的编程札记

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

一、方法一

1.1 思想

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

代码语言:javascript
复制
@param prefix 固定前缀@param valueToProcess 待处理的字符串

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

何时输出一个结果?

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

代码语言:javascript
复制
    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 ACC AB 的结果,与A BC 的结果一共产生六个结果,包括:

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

  • 第三步:

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

代码语言:javascript
复制
ABCACBBACBCACABCBA

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

代码语言:javascript
复制
/** * @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));        }    }    }

测试代码

代码语言:javascript
复制
/** * @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");    }
}

输出结果

代码语言:javascript
复制
AB的全排列:ABBAABC的全排列:ABCACBBACBCACABCBA

1.2 代码调整

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

代码语言:javascript
复制
valueToProcess.substring(0, i)  + valueToProcess.substring(i + 1, len)

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

代码语言:javascript
复制
    /**     * 返回一个不包含指定下标元素的字符串     * @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代码段替换掉。

代码语言:javascript
复制
    /**     * 递归处理     *      * @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中。

代码语言:javascript
复制
/** * @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中,

代码语言:javascript
复制
/** * @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全排列的过程如下图所示:

根据上述思想,编写代码如下:

代码语言:javascript
复制
/** *  * @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对象创建等,相比方法一来讲更好。方法一的优势在于比较好理解。

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

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

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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-09-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 孟君的编程札记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、方法一
  • 1.1 思想
    • 1.2 代码调整
    • 二、方法二(采用交换的算法)
    • 三、小结
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档