字符串全排列(permutation)（转）

问题：给定字符串S，生成该字符串的全排列。

方法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;

}

两种方法的生成结果：

view source

 

print?

method1

ABA

AAB

BAA

BAA

AAB

ABA

method2

ABA

AAB

BAA

请按任意键继续. . .