5

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

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

需要修复什么？

4

2 回答 2

18

您的方法有效（使用 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());在置换之前执行。

于 2013-06-09T06:27:08.367 回答
1

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

改变 

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

到

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

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

于 2013-06-09T05:45:56.130 回答