锐客网

  1. 首页 > it技术 > >

输出字符串中字符的所有排列

编写带有下列声明的例程：

public void permute(String str); private void permute(char[] str, int low, int high);

第一个例程是个驱动程序，它调用第二个例程并显示String str中的字符的所有排列。例如，str是"abc"， 那么输出的串则是abc，acb，bac，bca，cab，cba，第二个例程使用递归。
本文主要参考了字符串全排列算法学习-低调小一
这题主要使用到递归，递归的四条基本法则（数据结构与算法分析-Java语言描述page7）:
1、基准情形。必须总要有某些基准情形，无需递归就能解出。
2、不断推进。对于那些需要递归求解的情形，每一次递归调用都必须要使状况朝向一种基准情形推进。
3、设计法则。假设所有的递归调用都能运行。
4、合成效益法则。在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作。
对于字符串的排列问题：
如果能生成n-1个元素的全排列，就能生成n个元素的全排列。对于只有一个元素的集合，可以直接生成全排列。所以全排列的递归终止条件很明确，只有一个元素时。我们可以分析一下全排列的过程：
(1) 首先，我们固定第一个字符a，求后面两个字符bc的排列。
(2) 当两个字符bc排列求好之后，我们把第一个字符a和后面的b交换，得到bac，接着我们固定第一个字符b，求后面两个字符ac的排列。
(3) 现在是把c放在第一个位置的时候了，但是记住前面我们已经把原先的第一个字符a和后面的b做了交换，为了保证这次c仍是和原先处在第一个位置的a交换，我们在拿c和第一个字符交换之前，先要把b和a交换回来。在交换b和a之后，再拿c和处于第一位置的a进行交换，得到cba。我们再次固定第一个字符c，求后面两个字符b、a的排列。
(4) 既然我们已经知道怎么求三个字符的排列，那么固定第一个字符之后求后面两个字符的排列，就是典型的递归思路了。
下面这张图很清楚的给出了递归的过程：
输出字符串中字符的所有排列
文章图片

public static void permute(String str){ char[] ch = str.toCharArray(); permute(ch, 0, ch.length-1); }private static void permute(char[] str, int low, int high){ int length = str.length; if(low == high){ String s = ""; for(int i=0; i

由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。但是对bab，第二个数和第三个数不同，则需要交换，得到bba。由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。
换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数，所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！
这样，我们得到在全排列中去掉重复的规则：
去重的全排列就是从第一个数字起，每个数分别与它后面非重复出现的数字交换。
在原代码中加入如下改进代码：
for(int i=low; i

其中is_swap(char[] str, int m, int n)函数如下。
public static int is_swap(char[] str, int m, int n){ int flag = 1; for(int i=m; i

【输出字符串中字符的所有排列】至此该问题得到解决。

    推荐阅读


    上一篇：element 源码学习六 —— Carousel 走马灯学习

    下一篇：换个角度学习 VUE CLI 3