CODEWITHSUNDEEP
c++stringc++11
ninjakx
ninjakx

Reputation: 35

Generating permutation of the string in c++

This is the code which generates possible permutation using bit masking. I am having problem in understanding how is it executing after this condition when i = 2 , bit = 4 , mask = 7.

when bit is 4 and mask is 7 so condition (bit & mask) == true So it will continue .How i = 2 again ? and how mask becomes 1 when Mask will change when it will execute recurse(....)

#include <iostream>
#include <string>

using namespace std;

void recurse(string s, int mask = 0,string out = "")
{ 
  int n = s.length();
  if (out.length() == n) cout << ' ' << out<<endl;
  for (int i = 0; i < n; i++) {
    cout<<"I:"<<i<<"=>";
    unsigned bit = 1 << i;
    cout<<bit<< " -> " <<mask<<endl;
    cout<<"cond:"<<(mask & bit)<<endl;
    if (mask & bit) continue;
    cout<<out+s[i]<<endl;
    recurse(s, mask | bit, out + s[i]);
  }
}

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

Output:

I:0=>1 -> 0
cond:0
r
I:0=>1 -> 1
cond:1
I:1=>2 -> 1
cond:0
re
I:0=>1 -> 3
cond:1
I:1=>2 -> 3
cond:2
I:2=>4 -> 3
cond:0
red
 red
I:0=>1 -> 7
cond:1
I:1=>2 -> 7
cond:2
I:2=>4 -> 7     <===== here when bit is 4 and mask is 7 so condition (bit & mask) == true
cond:4              So it will continue .How i = 2 again ? and how mask becomes 1 when Mask will change when it will execute recurse(....)
I:2=>4 -> 1
cond:0
rd
I:0=>1 -> 5

Upvotes: 1

Views: 158

Answers (2)

kindanoob
kindanoob

Reputation: 623

Since you are using a recursive algorithm, you need to stop recursing when you reached the termination condition (in your case it is out.length() == n). If this condition is triggered, you print found permutation, but what happens immediately after this? You continue to execute the function. In particular, you will iterate through the for loop which will print some output (meaningless at this point, because you reached the bottom of recursion). In fact, you got confused by the output messages printed after the recursion termination condition triggered. Add the return statement to your check for recursion termination:

if (out.length() == n) {
    cout << "OUT: " << out << endl;
    return;
}

This way you will avoid redundant recursive calls and won't see irrelevant output messages that can be confusing.

As for your question about why mask doesn't change - note that for values of mask = 7 and bit = 4 you get maks | bit = 7| 4 = 7 = mask. So in some cases, bitwise OR-ing mask and bit will not affect the mask.

Upvotes: 2

Anders Wind
Anders Wind

Reputation: 21

After the continue i = 3, and since n = 3 the loop stops. So it goes up one recursion step and continues from the loop:

I:0=>1 -> 1
cond:1
I:1=>2 -> 1
cond:0
re

You can try printing a statement saying something like "finished loop" to see this.

I hope this answers your question.

Upvotes: 0

Related Questions