面试题28：字符串的排列

题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入“abc”，则打印出”abc”,”acb”,”bac”,”bca”,”cab”,”cba”。

分析

此题即求某个序列的全排列。此序列可以是数组或字符串等。求全排列的方法我介绍两种：

• 直接用STL算法
• 自己实现

套用STL的话非常简单，只需要包含头文件#include<algorithm>，然后使用下面代码即可：

```void Permutation(string str) { sort(str.begin(),str.end()); do { cout<<str<<endl; }while(next_permutation(str.begin(),str.end()); }

需要注意的是，以上代码在do-while循环之前必须保证字符串是有序的，否则会只输出部分的全排列序列。

自己实现的思想如下：

我们可以将字符串看成两部分：第一部分是第一个字符，第二部分是后面所有字符。先求出第一部分，然后可以递归地处理第二部分。 

而可能出现在第一部分的字符就是将所有字符与第一部分交换而得到的。

代码如下：

```void _Permutation(string str,int start,int end)
{
    if(start>=end)
        cout<<str<<endl;
    else
    {
        int i=start;
        for(i=start;i<end;++i)
        {
            swap(str[i],str[start]);
            _Permutation(str,start+1,end);
            swap(str[i],str[start]);
        }
    }
}

void Permutation(string str)
{
    if(str.size()<=0)
        return;
    _Permutation(str,0,str.size());
}

以上

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：点我前往