使用C语言解决字符串全排列问题
问题 思路
基本解决方法 #include <iostream> #include <string> using namespace std; void permute1(string prefix,string str) { if(str.length() == 0) cout << prefix << endl; else { for(int i = 0; i < str.length(); i++) permute1(prefix+str[i],str.substr(0,i)+str.substr(i+1,str.length())); } } void permute1(string s) { permute1("",s); } int main() { //method1,unable to remove duplicate permutations. cout << "method1" << endl; permute1("ABA"); } 优点:该方法易于理解,但无法移除重复的排列,如:s="ABA",会生成两个“AAB”。 方法2:利用交换的思想,具体见实例,但该方法不如方法1容易理解。 #include <iostream> #include <string> #include <cstdio> using namespace std; void swap(char* x,char* y) { char tmp; tmp = *x; *x = *y; *y = tmp; } /* Function to print permutations of string This function takes three parameters: 1. String 2. Starting index of the string 3. Ending index of the string. */ void permute(char *a,int i,int n) { int j; if (i == n) printf("%sn",a); else { for (j = i; j <= n; j++) { if(a[i] == a[j] && j != i) //为避免生成重复排列,当不同位置的字符相同时不再交换 continue; swap((a+i),(a+j)); permute(a,i+1,n); swap((a+i),(a+j)); //backtrack } } } int main() { //method2 cout << "method2" << endl; char a[] = "ABA"; permute(a,2); return 0; } 两种方法的生成结果: method1 ABA AAB BAA BAA AAB ABA method2 ABA AAB BAA 下面来看ACM题目实例 示例题目 题目描述: ac代码 #include <stdio.h> #include <stdlib.h> #include <string.h> struct seq { char str[7]; }; struct seq seqs[721]; int count; void swap(char *str,int a,int b) { char temp; temp = str[a]; str[a] = str[b]; str[b] = temp; } void permutation_process(char *name,int begin,int end) { int k; if (begin == end - 1) { strcpy(seqs[count].str,name); count ++; }else { for (k = begin; k < end; k ++) { swap(name,k,begin); permutation_process(name,begin + 1,end); swap(name,begin); } } } int compare(const void *p,const void *q) { const char *a = p; const char *b = q; return strcmp(a,b); } int main() { char name[7]; int i,len; while (scanf("%s",name) != EOF) { count = 0; len = strlen(name); permutation_process(name,len); qsort(seqs,count,sizeof(seqs[0]),compare); for (i = 0; i < count; i ++) { printf("%sn",seqs[i].str); } printf("n"); } return 0; } 去掉重复的全排列 由于全排列就是从第一个数字起,每个数分别与它后面的数字交换,我们先尝试加个这样的判断――如果一个数与后面的数字相同那么这两个数就不交换了。例如abb,第一个数与后面两个数交换得bab,bba。然后abb中第二个数和第三个数相同,就不用交换了。但是对bab,第二个数和第三个数不同,则需要交换,得到bba。由于这里的bba和开始第一个数与第三个数交换的结果相同了,因此这个方法不行。 换种思维,对abb,第一个数a与第二个数b交换得到bab,然后考虑第一个数与第三个数交换,此时由于第三个数等于第二个数,所以第一个数就不再用与第三个数交换了。再考虑bab,它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕! 这样,我们得到在全排列中去掉重复的规则: 贴出上面ac代码的去重版本: #include <stdio.h> #include <stdlib.h> #include <string.h> struct seq { char str[7]; }; struct seq seqs[721]; int count; int is_swap(char *str,int k) { int i,flag; for (i = begin,flag = 1; i < k; i ++) { if (str[i] == str[k]) { flag = 0; break; } } return flag; } void swap(char *str,int b) { char temp; temp = str[a]; str[a] = str[b]; str[b] = temp; } void permutation_process(char *name,int end) { int k; if (begin == end - 1) { strcpy(seqs[count].str,name); count ++; }else { for (k = begin; k < end; k ++) { if (is_swap(name,begin,k)) { swap(name,begin); permutation_process(name,end); swap(name,begin); } } } } int compare(const void *p,b); } int main() { char name[7]; int i,len; while (scanf("%s",compare); for (i = 0; i < count; i ++) { printf("%sn",seqs[i].str); } printf("n"); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |