Cracking the coding interview--Q8.4

January 11, 2013
作者:Hawstein
出处:http://hawstein.com/posts/8.4.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。



题目

原文:

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个字符了, 所以此时返回一个空的排列。代码如下:

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”的全序列。代码如下:

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;
}

完整代码如下:

#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