Implementing Heap's algorithm in C++

Question

I am trying to implement Heap's algorithm in C++. I feel I have written the code exactly as the algorithm works but it is giving wrong results.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void print(vector<int> v)

{ 
   for(auto x:v) 
            cout<<x;
   cout<<endl;
}

void gen(vector<int> v,int n)

{  
      if(v.size()==1) 
          cout<<v[0];
      print(v);
      int i = 0;
      while(i<n)
       {
          gen(v,n-1);
          if(n%2) 
               swap(v[n-1],v[0]);
          else 
               swap(v[n-1],v[i]);
          i++;
       }

}


int main()
{
  vector<int>  v  ={1,2,3};
  gen(v,v.size());
}

I am stuck at trying to make this work. For the vector in the above code, it gives the absurd result:

123 123 123 123 213 213 321 321 321 231 231 123 123 123 213 213

You probably didn't want gen(vector<int> v,int n) to pass v by-value, did you? — WhozCraig
– WhozCraig, Commented Jan 19, 2015 at 20:45
Considering that the function itself prints the results, that's less stupid than it looks at first sight. — MSalters
– MSalters, Commented Jan 19, 2015 at 20:47
@MSalters would be grateful if you could help however stupid it may be. I am stuck here. — ed bale
– ed bale, Commented Jan 19, 2015 at 20:50
@edbale I was just asking. Was your intent that gen modify the caller's vector? If so, yes, you're doing it wrong. If no, then no. — WhozCraig
– WhozCraig, Commented Jan 19, 2015 at 20:50

MSalters · Accepted Answer · 2015-01-19 21:01:31Z

4

The Wiki page shows an if-else that's missing from your code. The one if that you have does something completely different.

Also, I'd add a std::endl after the cout, and try with the input 1 2 3 4. The linked article has a line-by-line example of the algorithm running for 4 elements.

edited Jan 19, 2015 at 21:01

answered Jan 19, 2015 at 20:50

MSalters

182k11 gold badges171 silver badges376 bronze badges

Sign up to request clarification or add additional context in comments.

11 Comments

ed bale Over a year ago

that i think won't matter as it is just a check for single element vector which has only one permutation.

WhozCraig Over a year ago

@edbale it actually matters a great deal, since your code checks v.size() against 1, which it will never be. You're passing a 3-element vector in to this and doing nothing to change that. Pretty sure that v.size() should be n. Once that is done the else becomes very relevant.

MSalters Over a year ago

@edbale: That's where you misunderstood. Check the example on the right side of the page. The print call happens if and only if n=1. Since you need 6 permutations, you should have 6 calls to gen(v,1).

MSalters Over a year ago

@WhozCraig: For n==1, you should print more than just v[0]. The actual print(v) function is correct, it's just called far too often.

MSalters Over a year ago

@edbale: The best way to deal with that is to fix the question yourself. What output should the program produce? In particular, in which order? Try running the algorithm manually, on paper.

|

Collectives™ on Stack Overflow

Implementing Heap's algorithm in C++

1 Answer 1

11 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

11 Comments

Your Answer

Sign up or log in

Post as a guest

Related