偶看新闻给男人理发的女理发师:字符串全排列问题
来源：百度文库 编辑：偶看新闻 时间：2024/04/19 19:59:00
字符串全排列问题
问题：给定字符串S，生成该字符串的全排列。
方法1：依次从字符串中取出一个字符作为最终排列的第一个字符，对剩余字符组成的字符串生成全排列，最终结果为取出的字符和剩余子串全排列的组合。
#include#include 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两种方法的生成结果：#include #include 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(){//method2cout << "method2" << endl;char a[] = "ABA";permute(a,0,2);return 0;}
method1ABAAABBAABAAAABABAmethod2ABAAABBAA请按任意键继续. . .