使用位掩码生成排列

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 是字符串的长度。我正在跟踪到目前为止使用变量打印了多少个字符。在我调用的主函数中

recurse(s,0,0);

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

红色的

它的输出是

红鹿德德雷尔博士

我哪里错了？

---

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

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查找尚未在maskas 中标记的字符。每个找到的字符都会添加到输出中out。然后，递归调用对所有未采用的字符重复该过程。

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