問(wèn)題
輸入一個(gè)字符串，打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc，則輸出由字符a，b，c所能排列出來(lái)的所有字符串a(chǎn)bc，acb，bac，bca，cab和cba
思路
這是典型的遞歸求解問(wèn)題，遞歸算法有四個(gè)特性：
對(duì)于字符串的排列問(wèn)題：
如果能生成n-1個(gè)元素的全排列，就能生成n個(gè)元素的全排列。對(duì)于只有一個(gè)元素的集合，可以直接生成全排列。所以全排列的遞歸終止條件很明確，只有一個(gè)元素時(shí)。我們可以分析一下全排列的過(guò)程：
下面這張圖很清楚的給出了遞歸的過(guò)程：
基本解決方法
方法1：依次從字符串中取出一個(gè)字符作為最終排列的第一個(gè)字符，對(duì)剩余字符組成的字符串生成全排列，最終結(jié)果為取出的字符和剩余子串全排列的組合。
#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)點(diǎn)：該方法易于理解，但無(wú)法移除重復(fù)的排列，如：s="ABA"，會(huì)生成兩個(gè)“AAB”。
方法2：利用交換的思想，具體見(jiàn)實(shí)例，但該方法不如方法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) //為避免生成重復(fù)排列，當(dāng)不同位置的字符相同時(shí)不再交換 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;}兩種方法的生成結(jié)果：
method1ABAAABBAABAAAABABAmethod2ABAAABBAA
下面來(lái)看ACM題目實(shí)例
示例題目
題目描述
題目描述：
給定一個(gè)由不同的小寫字母組成的字符串，輸出這個(gè)字符串的所有全排列。
我們假設(shè)對(duì)于小寫字母有'a' < 'b' < ... < 'y' < 'z'，而且給定的字符串中的字母已經(jīng)按照從小到大的順序排列。
輸入：
輸入只有一行，是一個(gè)由不同的小寫字母組成的字符串，已知字符串的長(zhǎng)度在1到6之間。
輸出：
輸出這個(gè)字符串的所有排列方式，每行一個(gè)排列。要求字母序比較小的排列在前面。字母序如下定義：
已知S = s1s2...sk , T = t1t2...tk，則S < T 等價(jià)于，存在p (1 <= p <= k)，使得
s1 = t1, s2 = t2, ..., sp - 1 = tp - 1, sp < tp成立。
樣例輸入：
abc
樣例輸出：
abc
acb
bac
bca
cab
cba
提示：
每組樣例輸出結(jié)束后要再輸出一個(gè)回車。
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
****************************************************************/
去掉重復(fù)的全排列
上述代碼有個(gè)缺陷，就是會(huì)造成重復(fù)數(shù)據(jù)的輸出，例如abb這種字符串，上述程序跑完結(jié)果如圖：
由于全排列就是從第一個(gè)數(shù)字起，每個(gè)數(shù)分別與它后面的數(shù)字交換，我們先嘗試加個(gè)這樣的判斷――如果一個(gè)數(shù)與后面的數(shù)字相同那么這兩個(gè)數(shù)就不交換了。例如abb，第一個(gè)數(shù)與后面兩個(gè)數(shù)交換得bab，bba。然后abb中第二個(gè)數(shù)和第三個(gè)數(shù)相同，就不用交換了。但是對(duì)bab，第二個(gè)數(shù)和第三個(gè)數(shù)不同，則需要交換，得到bba。由于這里的bba和開(kāi)始第一個(gè)數(shù)與第三個(gè)數(shù)交換的結(jié)果相同了，因此這個(gè)方法不行。
換種思維，對(duì)abb，第一個(gè)數(shù)a與第二個(gè)數(shù)b交換得到bab，然后考慮第一個(gè)數(shù)與第三個(gè)數(shù)交換，此時(shí)由于第三個(gè)數(shù)等于第二個(gè)數(shù)，所以第一個(gè)數(shù)就不再用與第三個(gè)數(shù)交換了。再考慮bab，它的第二個(gè)數(shù)與第三個(gè)數(shù)交換可以解決bba。此時(shí)全排列生成完畢！
這樣，我們得到在全排列中去掉重復(fù)的規(guī)則：
去重的全排列就是從第一個(gè)數(shù)字起，每個(gè)數(shù)分別與它后面非重復(fù)出現(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; } 新聞熱點(diǎn)
疑難解答
圖片精選
