問題：給定字符串S，生成該字符串的全排列。

方法1：依次從字符串中取出一個字符作為最終排列的第一個字符，對剩余字符組成的字符串生成全排列，最終結(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)點：該方法易于理解，但無法移除重復的排列，如：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;
}