C++：列举字符串的排列

Question

我想向所有的程序员们提问，仅就 效率 这个问题。我目前正在解决一些可能会在面试中被问到的问题，其中涉及到著名的字符串 排列组合 问题。我下面所编写的代码可能是编程历史上最常见的事情之一，但是我不知道它的状态，因为我还没有查找过任何解决方案。

长话短说，我下面所编写的程序是否是一个合适的解决方案？或者它能否变得更加高效？我问这个问题是因为如果有一天我再次遇到这种情况，我想确保我已经实现了最佳的解决方案之一。

#include <iostream>
using namespace std;

int fac(int num)
{
    int result=1;
    for(int i=1;i<=num;i++)
        result*=i;
    return result;
}

int main(int argc, const char * argv[])
{
    string str="abcd";
    int limit=fac(str.size());
    int mod=str.size();
    for(int i=0;i<limit;i++){
        swap(str[i%mod],str[(i+1)%mod]);
        cout<<str<<endl;
    }
    return 0;
}

- Ali

---

你知道 std::next_permutation 吗？ - Blastfurnace

是的，我知道。但是因为它是一个标准库，而不是我想出来的解决方案，所以没有参考它。 - Ali

如果你不想让别人告诉你不要重复造轮子，那么这个问题应该发到 CodeReview.SE 而不是 SO。 - ildjarn

我非常感激自己从未经历过那种面试，以及他们可能会问的疯狂问题。这是咨询和/或教学背景的优势。您的声誉早已超越了您自己。 - Mike Dunlavey

Answer 1

不处理字符串中的重复字母，例如"aaabbb"。

- djechlin

---

谢谢您的反馈。我会仔细查看！顺便问一下，有什么建议吗？:D - Ali

Answer 2

您可以使用递归：

#include <iostream>
#include <tchar.h>
#include <string>

using namespace std;

void swap(char &first, char &second) {
    char tmp = first;
    first = second;
    second = tmp;
}

void enumPermutations(string &p, int m)
{
    if (m == p.size() - 1)
        cout << p << endl;
    else
        for (int j = m; j < p.size(); j++) {
            swap(p[j], p[m]);
            enumPermutations(p, m+1);
            swap(p[j], p[m]);
        }
}

int _tmain(int argc, _TCHAR* argv[])
{
    string str = "abcd";
    enumPermutations(str, 0);
    getchar();
    return 0;
}

（在Visual Studio中编译和测试）。

- Smi

---

可能会慢一些，但了解这些选项很有用（特别是为了面试准备）。 - djechlin

Answer 3

我已经通过使用 std::map 找到了解决方案。不认为它是那么低效的;

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int fac(int num)
{
    int result=1;
    for(int i=1;i<=num;i++)
        result*=i;
    return result;
}
int main(int argc, const char * argv[])
{
    string str="aabb";
    int limit=fac(str.size());
    int mod=str.size();
    std::map<string,bool>T;
    vector<string>permutations;
    for(int i=0;i<limit;i++){
        if(T[str]==0){
            permutations.push_back(str);
            T[str]=1;
        }
        swap(str[i%mod],str[(i+1)%mod]);
    }
    for(int i=0;i<permutations.size();i++)
        cout<<permutations[i]<<endl;
    return 0;
}

- Ali

---

如果你愿意使用标准库，为什么不使用std::next_permutation呢？我不明白。 - ildjarn

实现自己的解决方案是有价值的，这是一个很好的练习。当然，如果你想要“完成任务”并提高生产力，使用标准库会更好。 - Blastfurnace

Answer 4

你的问题的答案是不行。在确定解决方案可行之前，你不应该担心其效率。而这个解决方案并不可行。

以下内容证明了这一事实。

ben-tillys-macbook-pro:ton btilly$ cat foo.cc
#include <iostream>
using namespace std;

int fac(int num)
{
    int result=1;
    for(int i=1;i<=num;i++)
        result*=i;
    return result;
}

int main(int argc, const char * argv[])
{
    string str="abcd";
    int limit=fac(str.size());
    int mod=str.size();
    for(int i=0;i<limit;i++){
        swap(str[i%mod],str[(i+1)%mod]);
        cout<<str<<endl;
    }
    return 0;
}
ben-tillys-macbook-pro:ton btilly$ g++ foo.cc
ben-tillys-macbook-pro:ton btilly$ ./a.out | wc
      24      24     120
ben-tillys-macbook-pro:ton btilly$ ./a.out | sort -u | wc
      12      12      60
ben-tillys-macbook-pro:ton btilly$ ./a.out | grep bdc
ben-tillys-macbook-pro:ton btilly$ 

- btilly

---

我已经纠正了代码。请检查我的答案，感谢您的贡献。 - Ali