字符串的全排列【递归算法训练】
前几天，师兄轻描淡写的出了一道题，对于一个给定的字符串，输出它的全排列结果，例如，输入ab，则程序需要输出ab,ba[结果数为2*1=2]。额外的要求是对于字符串中的重复字符，程序要能识别出来并进行去重处理，例如，输入aab，则程序需要输出baa,aba,aab[结果数为3，而不是3*2=6]。
这里我用了两种思路实现了这道题，不过都属于递归，第一种思路是我自己想的，只能输出全排列，在去重处理上尚需完善[例如，输入aab，程序可以得到正确结果；但如果输入aaba，程序就得不到完全去重的结果了，即重复字符只能连续出现，否则程序就会出现bug，究其原因还是递归时记不住以前处理的结果，如果记录这些结果，则空间开销太大，而且每次都要检查是否与以前的结果相同，付出的时间代价也很大]。
第二种思路是另一位师兄指点我的，在他提出的方案基础上，我做了完善，不但可以输出全排列，而且可以达到去重要求，算是一个完整的算法。
第一种思路：求字符串a{n}的全排列，可以分解为求a{n – 1}的全排列，对于a{n – 1}的每一个全排列结果，只要将a[n]插入到a{n – 1}序列的n个位置中，即可得到a{n}的全排列结果。例如：求abc的全排列，可以先求ab的全排列，再将c插入到第0,1,2位即可得到abc的全排列，而对于ab的全排列，可以先求a的全排列，再将b插入到第0,1位即可得到ab全排列结果，因为a是单个字符，它的全排列结果只有一个：a，所以递归开始返回，层层向上，得到abc的全排列的解。总结：这是基于插入操作的算法！
第二种思路：求字符串a{n}的全排列，首先将a[0]和a[n]调换，然后求前面长度为n – 1的字符串的全排列，完成后，将a{n}序列恢复原样，再将a[1]和a[n]调换，以此类推，香港虚拟主机，直到a[n]和a[n]调换，去求前面长度为n – 1的字符串的全排列，至此所有的结果均已得到。例如：求abc的全排列，可以先将a和c调换并固定a，即cba，此时求cb的全排列，将c和b调换并固定c，即bca，由于b是一个单独的字符串，此次递归到底层，输出一个结果bca，返回，回归原样为cba，此时下一个需要处理的值是b，美国服务器，即b和b调换【即a[i]和a[n]调换，但此时i恰好等于n】，得到cba，由于c是单独的字符串，递归到底层，输出一个结果cba，返回，回归原样为cba，因为i已经等于n，则继续返回，回归原样abc，此时a已经处理完毕，再将b放在最末尾固定，进行处理，以此类推，得到所有全排列结果。这个思路有一个好处，即付出少量的空间代价即可达到去重处理的要求，对于重复的字符，美国空间，程序只要发现这个字符曾经在i位置固定过，就不再进行此轮处理，因为对于任意字符m，在i位置固定过，则可知m在i位置的前提下整个字符串的全排列结果已经得到，那么相同的字符再一次固定在相同的位置，处理的全排列必然导致结果重复。总结：这是基于调换操作的算法！
第一种思路的源代码【不完整，去重还有bug】：
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h>count = insert({ 9int i;10int j;11char temp[10];12int step;13for(i = 0; i < nowlength; i ++)14 {15temp[i] = a[i];temp[i] = ;18for(j = 0; j <= nowlength; j ++)19 {20for(i = 0; i < nowlength; i ++)21 {22a[i] = temp[i];(a[j] == b){26step = 1;27for(i = j + 1; i < nowlength; i ++)28 {29if(a[i] == b)30 {31step ++;32 }{35break;36 }37 }38 }{41step = 0;42 }43for(i = nowlength; i > j; i –)44 {45a[i] = a[i – 1];46 }j += step;49if(nowlength + 1 < strlen(a))50 {}{, a);count ++;57 }58 }59 } main()62 {63char a[10];(scanf(,a) != EOF)66 {67count = 0;68if(strlen(a) == 1)69 {, a););72 }{75insert(a, 1, a[1]);,count);77 }78 };80 }
第二种思路【完整，可全排列亦可去重】：
读书破万卷，下笔如有神。
