Generate permutation using bitmask

Question

I am generating all permutations of a string using bitmask.

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

In this function n is the length of the string. I am keeping track of how many characters are printed so far using taken variable. In the main function I am calling

recurse(s,0,0);

But this is not working correctly. For input

red

Its output is

red de erd dr dre er

Where I am going wrong?

---

UPDATE // Below code works fine.

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

Here is another version. It's different from the questioner's code in 2 ways:

1. The parameter taken can be omitted and we can use mask + 1 == (1 << n) instead. It basically checks if bits 1 to n-1 of mask are all 1's. If so, then the recursion depth is n and we print the permutation.

2. Copying the string pref in each iteration can be slow if the size of the string is large. We can instead use a reference.

#include <iostream>
#include <string>

using namespace std;

void recurse(string s, int mask, string &pref);

int n = 3;

int main()
{
    string pref("");
    recurse(string("abc"), 0, pref);
    return 0;
}

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

where n is the size of the string. The output is

abc
acb
bac
bca
cab
cba

Answer 2

Actually, the questioner provided the answer himself. (Congratulation.)

As I already started to fiddle (couldn't resist) I want to present my solution as well:

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

Compiled and tested:

 red rde erd edr dre der

recurse() iterates through all characters of s looking for one which is not already marked in the mask as taken. Each found characters is added to output out. Then, the recursive call repeats it for all untaken characters.

Check out the sample code yourself on ideone.

Answer 3

Permutation tree for 'abc'

Your first code was visiting each node of this tree once and printing a character. So it was giving wrong output.

On a different note, you have used some redundant variables.

Instead of n you should use s.size().

In the second code instead of taken you you should use pref.size().