使用C語言解決字符串全排列問題
問題
輸入一個字符串,打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則輸出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba
思路
這是典型的遞歸求解問題,遞歸算法有四個特性:
- 必須有可達到的終止條件,否則程序陷入死循環(huán)
- 子問題在規(guī)模上比原問題小
- 子問題可通過再次遞歸調(diào)用求解
- 子問題的解應能組合成整個問題的解
對于字符串的排列問題:
如果能生成n-1個元素的全排列,就能生成n個元素的全排列。對于只有一個元素的集合,可以直接生成全排列。所以全排列的遞歸終止條件很明確,只有一個元素時。我們可以分析一下全排列的過程:
- 首先,我們固定第一個字符a,求后面兩個字符bc的排列
- 當兩個字符bc排列求好之后,我們把第一個字符a和后面的b交換,得到bac,接著我們固定第一個字符b,求后面兩個字符ac的排列
- 現(xiàn)在是把c放在第一個位置的時候了,但是記住前面我們已經(jīng)把原先的第一個字符a和后面的b做了交換,為了保證這次c仍是和原先處在第一個位置的a交換,我們在拿c和第一個字符交換之前,先要把b和a交換回來。在交換b和a之后,再拿c和處于第一位置的a進行交換,得到cba。我們再次固定第一個字符c,求后面兩個字符b、a的排列
- 既然我們已經(jīng)知道怎么求三個字符的排列,那么固定第一個字符之后求后面兩個字符的排列,就是典型的遞歸思路了
下面這張圖很清楚的給出了遞歸的過程:
基本解決方法
方法1:依次從字符串中取出一個字符作為最終排列的第一個字符,對剩余字符組成的字符串生成全排列,最終結果為取出的字符和剩余子串全排列的組合。
#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"); }
優(yōu)點:該方法易于理解,但無法移除重復的排列,如: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("%s\n", 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,0,2); return 0; }
兩種方法的生成結果:
method1 ABA AAB BAA BAA AAB ABA method2 ABA AAB BAA
下面來看ACM題目實例
示例題目
題目描述
題目描述:
給定一個由不同的小寫字母組成的字符串,輸出這個字符串的所有全排列。
我們假設對于小寫字母有'a' < 'b' < ... < 'y' < 'z',而且給定的字符串中的字母已經(jīng)按照從小到大的順序排列。
輸入:
輸入只有一行,是一個由不同的小寫字母組成的字符串,已知字符串的長度在1到6之間。
輸出:
輸出這個字符串的所有排列方式,每行一個排列。要求字母序比較小的排列在前面。字母序如下定義:
已知S = s1s2...sk , T = t1t2...tk,則S < T 等價于,存在p (1 <= p <= k),使得
s1 = t1, s2 = t2, ..., sp - 1 = tp - 1, sp < tp成立。
樣例輸入:
abc
樣例輸出:
abc
acb
bac
bca
cab
cba
提示:
每組樣例輸出結束后要再輸出一個回車。
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, k, 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, 0, len); qsort(seqs, count, sizeof(seqs[0]), compare); for (i = 0; i < count; i ++) { printf("%s\n", seqs[i].str); } printf("\n"); } return 0; }
/**************************************************************
Problem: 1120
User: wangzhengyi
Language: C
Result: Accepted
Time:710 ms
Memory:920 kb
****************************************************************/
去掉重復的全排列
上述代碼有個缺陷,就是會造成重復數(shù)據(jù)的輸出,例如abb這種字符串,上述程序跑完結果如圖:
由于全排列就是從第一個數(shù)字起,每個數(shù)分別與它后面的數(shù)字交換,我們先嘗試加個這樣的判斷——如果一個數(shù)與后面的數(shù)字相同那么這兩個數(shù)就不交換了。例如abb,第一個數(shù)與后面兩個數(shù)交換得bab,bba。然后abb中第二個數(shù)和第三個數(shù)相同,就不用交換了。但是對bab,第二個數(shù)和第三個數(shù)不同,則需要交換,得到bba。由于這里的bba和開始第一個數(shù)與第三個數(shù)交換的結果相同了,因此這個方法不行。
換種思維,對abb,第一個數(shù)a與第二個數(shù)b交換得到bab,然后考慮第一個數(shù)與第三個數(shù)交換,此時由于第三個數(shù)等于第二個數(shù),所以第一個數(shù)就不再用與第三個數(shù)交換了。再考慮bab,它的第二個數(shù)與第三個數(shù)交換可以解決bba。此時全排列生成完畢!
這樣,我們得到在全排列中去掉重復的規(guī)則:
去重的全排列就是從第一個數(shù)字起,每個數(shù)分別與它后面非重復出現(xiàn)的數(shù)字交換。
貼出上面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 begin, 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 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 ++) { if (is_swap(name, begin, k)) { swap(name, k, begin); permutation_process(name, begin + 1, end); swap(name, k, 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, 0, len); qsort(seqs, count, sizeof(seqs[0]), compare); for (i = 0; i < count; i ++) { printf("%s\n", seqs[i].str); } printf("\n"); } return 0; }