参考答案

方法1：依次从字符串中取出一个字符作为最终排列的第一个字符，对剩余字符组成的字符串生成全排列，最终结果为取出的字符和剩余子串全排列的组合。

#include#includeusing 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(void) {
	 //method1, unable to remove duplicate permutations. 
	 permute1("abc"); 
	 return 0;
} 

	优点：该方法易于理解，但无法移除重复的排列，如：s="ABA"，会生成两个“AAB”。 



	方法2：利用交换的思想，具体见实例，但该方法不如方法1容易理解。 

 

	

	我们以三个字符abc为例来分析一下求字符串排列的过程。首先我们固定第一个字符a，求后面两个字符bc的排列。当两个字符bc的排列求好之后，我们把第一个字符a和后面的b交换，得到bac，接着我们固定第一个字符b，求后面两个字符ac的排列。现在是把c放到第一位置的时候了。记住前面我们已经把原先的第一个字符a和后面的b做了交换，为了保证这次c仍然是和原先处在第一位置的a交换，我们在拿c和第一个字符交换之前，先要把b和a交换回来。在交换b和a之后，再拿c和处在第一位置的a进行交换，得到cba。我们再次固定第一个字符c，求后面两个字符b、a的排列。 



	既然我们已经知道怎么求三个字符的排列，那么固定第一个字符之后求后面两个字符的排列，就是典型的递归思路了。 



	基于前面的分析，我们可以得到如下的参考代码： 



void Permutation(char* pStr, char* pBegin)  
{  
    assert(pStr && pBegin);  
    //if(!pStr || !pBegin)  
        //return ;  
    if(*pBegin == '\0')  
        printf("%s\n",pStr);  
    else  
    {  
	        char temp;  
	        for(char* pCh = pBegin; *pCh != '\0'; pCh++)  
	        {  
	            if(pCh != pBegin && *pCh == *pBegin)   //为避免生成重复排列，当不同位置的字符相同时不再交换  
	                continue;  
	            temp = *pCh;  
	            *pCh = *pBegin;  
	            *pBegin = temp;  
	  
	            Permutation(pStr, pBegin+1);  
	  
	            temp = *pCh;  
	            *pCh = *pBegin;  
	            *pBegin = temp;  
	        }  
	}  
}  
	  
int main(void)  
{  
	char str[] = "aba";  
	Permutation(str,str);  
	return 0;  
}  

如p([1,2,3])输出：

	 [1]、[2]、[3]、[1,2]、[2,3]、[1,3]、[1,2,3]

这两问可以用伪代码。