题目
原文：
Write a method to compute all permutations of a string
译文：
写一个函数返回一个串的所有排列
解答
对于一个长度为n的串，它的全排列共有A(n, n)=n!种。这个问题也是一个递归的问题， 不过我们可以用不同的思路去理解它。为了方便讲解，假设我们要考察的串是”abc”， 递归函数名叫permu。
思路一：
我们可以把串“abc”中的第0个字符a取出来，然后递归调用permu计算剩余的串“bc” 的排列，得到{bc, cb}。然后再将字符a插入这两个串中的任何一个空位(插空法)， 得到最终所有的排列。比如，a插入串bc的所有(3个)空位，得到{abc,bac,bca}。 递归的终止条件是什么呢？当一个串为空，就无法再取出其中的第0个字符了， 所以此时返回一个空的排列。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef vector<string> vs;
vs permu(string s){
vs result;
if(s == ""){
result.push_back("");
return result;
}
string c = s.substr(0, 1);
vs res = permu(s.substr(1));
for(int i=0; i<res.size(); ++i){
string t = res[i];
for(int j=0; j<=t.length(); ++j){
string u = t;
u.insert(j, c);
result.push_back(u);
}
}
return result; //调用result的拷贝构造函数，返回它的一份copy，然后这个局部变量销毁(与基本类型一样)
}
思路二：
我们还可以用另一种思路来递归解这个问题。还是针对串“abc”， 我依次取出这个串中的每个字符，然后调用permu去计算剩余串的排列。 然后只需要把取出的字符加到剩余串排列的每个字符前即可。对于这个例子， 程序先取出a，然后计算剩余串的排列得到{bc,cb}，然后把a加到它们的前面，得到 {abc,acb}；接着取出b，计算剩余串的排列得到{ac,ca}，然后把b加到它们前面， 得到{bac,bca}；后面的同理。最后就可以得到“abc”的全序列。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vs permu1(string s){
vs result;
if(s == ""){
result.push_back("");
return result;
}
for(int i=0; i<s.length(); ++i){
string c = s.substr(i, 1);
string t = s;
vs res = permu1(t.erase(i, 1));
for(int j=0; j<res.size(); ++j){
result.push_back(c + res[j]);
}
}
return result;
}
完整代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
using namespace std;
typedef vector<string> vs;
vs permu(string s){
vs result;
if(s == ""){
result.push_back("");
return result;
}
string c = s.substr(0, 1);
vs res = permu(s.substr(1));
for(int i=0; i<res.size(); ++i){
string t = res[i];
for(int j=0; j<=t.length(); ++j){
string u = t;
u.insert(j, c);
result.push_back(u);
}
}
return result; //调用result的拷贝构造函数，返回它的一份copy，然后这个局部变量销毁(与基本类型一样)
}
vs permu1(string s){
vs result;
if(s == ""){
result.push_back("");
return result;
}
for(int i=0; i<s.length(); ++i){
string c = s.substr(i, 1);
string t = s;
vs res = permu1(t.erase(i, 1));
for(int j=0; j<res.size(); ++j){
result.push_back(c + res[j]);
}
}
return result;
}
int main(){
string s = "abc";
vs res = permu1(s);
for(int i=0; i<res.size(); ++i)
cout<<res[i]<<endl;
return 0;
}
全书题解目录：
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上：
https://github.com/Hawstein/cracking-the-coding-interview
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2013/01/11/8.4/
