补充全排列算法C语言实现

《补充全排列算法C语言实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、字符串全排列算法C语言实现问题描述：输入一个字符串，打印出该字符串中字符的所有排列。输入:123输出:123132213231312321问题分析：现象分析：这种问题，从直观感觉就是用递归方法来实现即：把复杂问题逐渐简单化，进而得出具体代码实现。（如何发现一个问题可以使用递归方式来解决？经分析可以发现：M个数的排列方法与N(N>M)个数的排列方法没有区别，处理方法与数据的个数没有关系。处理方法的一致性，就可以采用递归）。3个数（123）排列，第一位1不动，剩下两个数（23）的排列，只要相互颠倒一下，就可以出现关于1开头的所有排列123132把2换到第一位，保持不动，剩下的两个数（13）的排列

2、，只要相互颠倒一下，就可以出现关于2开头的所有排列213231同理，把3换到第一位，可得到312321扩展：把3个数的所有排列，前面加一个4，就可以得到关于4开头的所有的排列412341324213423143124321若把4与后续数据中的任意一个数据交换，通过完成对后续三个数的全排列，就可以得到相应的数开头的四数的排列。总结：对4个数的排列，可以转换成首位不动，完成对3个数的排列对3个数的排列，可以转换成首位不动，完成对2个数的排列对2个数的排列，可以转换成首位不动，完成对1个数的排列对于1个数，无排列，直接输出结果算法实现说明：对n个数的排列，分成两步：（1）首位不动，完成对n-1个数

3、的排列，（2）循环将后续其他数换到首位，再次进行n-1个数的排列注：排列完成后，最终的串要与原串相同C语言代码实现：#include#include//将串左移一位，首位存到末尾。voidshift(char*s){if(!s

4、

5、!s[0])return;//securitycode.nullstringcharch=s[0];inti=0;while(s[++i])s[i-1]=s[i];s[i-1]=ch;}//本函数对于一个已排序好的数据进行全排列voidpermutation(charlist[],inthead){inti,len;len=st

6、rlen(list);if(len-head==1)//后续没有再排列的，则输出排列数据{printf("%s",list);}else{for(i=k;i

7、复数据出现在待排列的数据中，则，若某数已经当过队首，则与其相同的数再当队首是一样的排列结果，如：1233进行全排列当第一个3当队首时，会出现一次全排列第二个3当队首时，会出现与第一个3当队首相同的全排列，因此，只需要保证此数据出现过队首时，不要让其再当队首就可以解决问题了。代码实现：//检查chk位的数据是否曾经当过队首/*list:待排列的全部数据chk:待检查的位置begin:已当过队首的数据的起始位置。因为是移位，所以，从begin检查到list尾就可以了。*/is_dup(char*list,intbegin,intchk){inti;for(i=begin;list[i];i++)

8、if(list[chk]==list[i])return1;return0;}voidpermutation(charlist[],intk){inti,len;len=strlen(list);if(len-k==1)//后续没有再排列的，则输出排列数据{printf("%s",list);}else{for(i=k;i

9、(char*a,char*b){charm;m=*a;*a=*b;*b=m;}//检查某数据是否曾经当过队首（在已交换过的数据中进行查找）/*list:待排列的全部数据end:当前交换的位置begin:待交换的位置*/intis_dup(char*s,intend,intbegin){inti=0;for(i=end;i>begin;i--)if(s[end]==s[i-1])return1;return0;