全排列是将一组数按一定顺序进行排列,如果这组数有n个,那么全排列数为n!个。我们在此需要考虑重复情况。应用递归算法实现排序。
1.如下程序,可实现全排列,但是缺少判断函数不能处理重复情况。
#include <stdio.h>int permutation( char s[], int b, int e ){ if( 0 <=b && b <= e) { if( b == e ) { PRintf( "%s/n",s); } else { int i; for( i=b; i<=e; i++) { char c = s[b]; s[b] = s[i]; s[i] = c; permutation( s, b+1, e); c = s[b]; s[b] = s[i]; s[i] = c; } } }}int main() { char s[] = "123"; permutation( s,0,2); return 0;}2.加入判断函数后可处理重复情况。#include <stdio.h>int is_swap(char s[], int begin, int k){ int i; for (i = begin; i < k; i ++) if(*(s + i) == *(s + k)) return 0; return 1;}void permutation(char s[], int b, int e){ if( (0 <= b) && (b <= e) ) { if( b == e ) { printf("%s/n", s); } else { int i = 0,m = 0,zx = 1; for(i=b; i<=e; i++) if(is_swap(s,b,i)) { char c = s[b]; s[b] = s[i]; s[i] = c; permutation(s, b+1, e); c = s[b]; s[b] = s[i]; s[i] = c; } } }}int main(){ char s[] = "aabb"; permutation(s, 0, sizeof(s) - 2); printf("%d",sizeof(s)); return 0;}3.优化,写出交换函数,直接调用调换函数进行调换。#include <stdio.h>//#include <stdlib.h>#include <string.h>void swap(char *str, int begin, int k){ char tmp; tmp = *(str + begin); *(str + begin) = *(str + k); *(str + k) = tmp;}int is_swap(char *str, int begin, int k){ int i; for (i = begin; i < k; i ++) if(*(str + i) == *(str + k)) return 0; return 1;}void permutation(char *str, int begin, int end){ int k; if (begin == (end - 1)) { printf("%s/n", str); return; } for (k = begin; k < end; k++) if(is_swap(str, begin, k)) { swap(str, begin, k); permutation(str, begin + 1, end); swap(str, begin, k); }}int main(void){ char str[10]; int length; gets(str); length = strlen(str); printf("%d/n", length); permutation(str, 0, length); return 0;}
新闻热点
疑难解答