問題
輸入一個字符串，打印出該字符串中字符的所有排列。例如輸入字符串abc，則輸出由字符a，b，c所能排列出來的所有字符串abc，acb，bac，bca，cab和cba
思路
這是典型的遞歸求解問題，遞歸算法有四個特性：
對于字符串的排列問題：
如果能生成n-1個元素的全排列，就能生成n個元素的全排列。對于只有一個元素的集合，可以直接生成全排列。所以全排列的遞歸終止條件很明確，只有一個元素時。我們可以分析一下全排列的過程：
下面這張圖很清楚的給出了遞歸的過程：
基本解決方法
方法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");}優點：該方法易于理解，但無法移除重復的排列，如：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;}兩種方法的生成結果：
method1ABAAABBAABAAAABABAmethod2ABAAABBAA
下面來看ACM題目實例
示例題目
題目描述
題目描述：
給定一個由不同的小寫字母組成的字符串，輸出這個字符串的所有全排列。
我們假設對于小寫字母有'a' < 'b' < ... < 'y' < 'z'，而且給定的字符串中的字母已經按照從小到大的順序排列。
輸入：
輸入只有一行，是一個由不同的小寫字母組成的字符串，已知字符串的長度在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
****************************************************************/
去掉重復的全排列
上述代碼有個缺陷，就是會造成重復數據的輸出，例如abb這種字符串，上述程序跑完結果如圖：
由于全排列就是從第一個數字起，每個數分別與它后面的數字交換，我們先嘗試加個這樣的判斷――如果一個數與后面的數字相同那么這兩個數就不交換了。例如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 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; } 新聞熱點
疑難解答
圖片精選
