在c ++中查找字符串的所有排列

Question

以下是打印给定字符串的所有排列的代码.代码编译但不打印任何内容.

using namespace std;

void RecPermute(string, string);

int main() {
    RecPermute("", "abc");
    return 0;
}

void RecPermute(string soFar, string rest) {
    if (rest == " ") {
        cout << soFar << endl;
    } else {
        for(int i=0; i<rest.length(); i++) {
            string next = soFar + rest[i];
            string remaining = rest.substr(0, i) + rest.substr(i+1);
            RecPermute(next, remaining);
    }
    }
}

需要修复什么？

Answer 1

你的方法是有效的(具有greedybuddha提供的正确条件),但可以更简单地实现(如chris所示).

#include <algorithm>
#include <iostream>
#include <string>

int main()
{
    std::string s("abcdefg");
    do
    {
        std::cout << s << "\n";
    }
    while ( std::next_permutation(s.begin(), s.end()) );
}

那它做了什么？std::next_permutation需要两个迭代器,一个是字符串的开头,第二个是结尾,所以基本上你说的是"考虑整个字符串".它置换字符串s,以便在调用之后,s包含在前一个值之后直接以字典顺序出现的唯一排列s.如果s是最后一个这样的排列(即输入"abcdefg"的"gfedcba"),则std::next_permutation返回false,因此您知道自己已完成.

由于您没有使用此代码创建任何新的(临时)字符串,因此它不仅更具可读性,而且更快.在我的机器上,对于"abcdefghij",你的算法大约需要5秒钟,std::next_permutation在不到一秒的时间内完成.对于另一个角色,它变得更糟,到54秒对6.8秒.

请注意,如果初始字符串未排序,则不会提供完整的排列列表.但当然有一个简单的解决方案:std::sort(s.begin(), s.end());在置换之前执行.

Answer 2

所以你们是如此的接近。您只需要匹配空字符串而不是空格。您可以通过匹配空字符串来做到这一点""。

改变

if (rest == " ") { ... }

到

if (rest == "") { ... }

你忘记了rest.substr(i+1)的长度，它应该是(i+1,i-3);