c++ - 使用位掩码生成排列

Question

我正在使用位掩码生成字符串的所有排列。

void recurse(string s, int mask,int taken){

    if(taken == n){
        cout << " ";
        return;
    }
    for(int i = 0; i < n; i++){
        if(((1 << i) & mask) == 0){
            cout << s[i];
            recurse(s, (mask|(1 << i)), taken + 1);
        }
    }
}

在这个函数中，n 是字符串的长度。我正在跟踪到目前为止使用 taken 变量打印了多少个字符。在我调用的主函数中

recurse(s,0,0);

但这不能正常工作。用于输入

red

它的输出是

red de erd dr dre er

我哪里错了？

---

更新//下面的代码工作正常。

void recurse(string s, int mask,int taken, string pref){

    if(taken == n){
        cout << pref <<endl; 
        return;
    }
    for(int i = 0; i < n; i++){
        if(((mask >> i) & 1) == 0){
            recurse(s,(mask | (1 << i)),taken + 1, pref + s[i]);
        }
    }
}

Answer 1

其实是提问者自己给出了答案。 (祝贺。)

因为我已经开始摆弄(无法抗拒)我也想展示我的解决方案:

#include <iostream>
#include <string>

using namespace std;

void recurse(
  const string &s, unsigned mask = 0, const string &out = string())
{
  size_t n = s.size();
  if (out.size() == n) cout << ' ' << out;
  for (size_t i = 0; i < n; ++i) {
    unsigned bit = 1 << i;
    if (mask & bit) continue;
    recurse(s, mask | bit, out + s[i]);
  }
}

int main()
{
  string test = "red";
  recurse(test);
  cout << endl;
  return 0;
}

编译和测试:

 red rde erd edr dre der

recurse() 遍历 s 的所有字符，寻找尚未在 mask 中标记的字符。每个找到的字符都被添加到输出 out。然后，递归调用对所有未使用的字符重复它。

自己在 ideone 上查看示例代码.