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

字符串全排列算法C语言实现问题描述：输入一个字符串，打印出该字符串中字符的所有排列。输入:123输出:123132213231312321问题分析：现象分析：这种问题，从直观感觉就是用递归方法来实现即：把复杂问题逐渐简单化，进而得出具体代码实现。（如何发现一个问题可以使用递归方式来解决？ 经分析可以发现：M个数的排列方法与N(NM)个数的排列方法没有区别，处理方法与数据的个数没有关系。处理方法的一致性，就可以采用递归）。3个数（123）排列，第一位1不动，剩下两个数（23）的排列，只要相互颠倒一下，就可以出现关于1开头的所有排列 123 132把2换到第一位，保持不动，剩下的两个数（13）的排列，只要相互颠倒一下，就可以出现关于2开头的所有排列 213 231同理，把3换到第一位，可得到 312 321扩展：把3个数的所有排列，前面加一个4，就可以得到关于4开头的所有的排列412341324213423143124321若把4与后续数据中的任意一个数据交换，通过完成对后续三个数的全排列，就可以得到相应的数开头的四数的排列。总结：对4个数的排列，可以转换成首位不动，完成对3个数的排列对3个数的排列，可以转换成首位不动，完成对2个数的排列对2个数的排列，可以转换成首位不动，完成对1个数的排列对于1个数，无排列，直接输出结果算法实现说明：对n个数的排列，分成两步：（1）首位不动，完成对n-1个数的排列，（2）循环将后续其他数换到首位，再次进行n-1个数的排列注：排列完成后，最终的串要与原串相同C语言代码实现： #include #include /将串左移一位，首位存到末尾。void shift( char *s )if ( !s|!s0 ) return ; /security code . null stringchar ch=s0;int i=0;while( s+i )si-1=si ;si-1=ch;/本函数对于一个已排序好的数据进行全排列void permutation(char list, int head ) int i,len; len=strlen(list) ; if ( len-head = 1 ) /后续没有再排列的，则输出排列数据 printf( %sn, list ); else for (i = k; ilen; i+) /从当前位置开始，每个数当一次队首，并进行后续排列 permutation(list, head+1); /后续串排列shift( &listhead ); /轮流为当第一 void pailie( char *str ) permutation( str, 0 ); /排列算法，从串的第几位开始排列 int main() char str=1234; pailie(str); return 0;带重复数据的排列问题：如果有重复数据出现在待排列的数据中，则，若某数已经当过队首，则与其相同的数再当队首是一样的排列结果，如：1233进行全排列当第一个3当队首时，会出现一次全排列第二个3当队首时，会出现与第一个3当队首相同的全排列，因此，只需要保证此数据出现过队首时，不要让其再当队首就可以解决问题了。代码实现：/检查chk位的数据是否曾经当过队首/*list:待排列的全部数据 chk:待检查的位置 begin:已当过队首的数据的起始位置。因为是移位，所以，从begin检查到list尾就可以了。*/is_dup( char *list, int begin, int chk )int i;for( i=begin; listi; i+ )if ( listchk = listi )return 1;return 0;void permutation(char list, int k) int i,len; len=strlen(list) ; if ( len-k = 1 ) /后续没有再排列的，则输出排列数据 printf( %sn, list ); else for (i = k; ibegin;i- )if ( send = si-1 )return 1;return 0;void permutation(char list, int k) int i,len; len=strlen(list) ; if ( len-k = 1 ) /后续没有再排列的，则输出排列数据 printf( %sn, list ); else for (i = k; ilen; i+) if ( !is_dup ( list,i,k ) ) /如果没有重复的，则进行相应的排列,否则跳过之，因为：相同的数据当队首，交换没有意义swap(&listk, &listi);/交换permutation(list, k+1); /后续串排列swap(&listi, &listk);/恢复 void p