ビットマスクを使用して順列を生成する

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

を呼び出しています。しかし、これは正しく動作していない主な機能には 。 入力

赤

ために、その出力は、私が間違っているつもりです

赤

デERD DR DRE ER

のですか？

---

UPDATE //コード以下は正常に動作します。

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()反復してmaskに記載されていない文字を検索するsのすべての文字。見つかった各文字は、出力outに追加されます。その後、再帰呼び出しは、未処理のすべての文字に対して繰り返します。

ideoneでサンプルコードをご確認ください。

Answer 2

あなたの最初のコードはたら、この木の各ノードを訪問し、文字を印刷しました。それは間違った出力を与えていました。

いくつかの冗長変数を使用しています。

nの代わりにs.size()を使用してください。

takenではなく2番目のコードでは、pref.size()を使用する必要があります。