Ttdfjt

The task is to compute all the permutations for a given vector of integers (but of course the specific integer type is not relevant for the solution)

The strategy is based on recursion + iterations

At each recursion, the state consists of

• the root sequence a which is the set of elements already placed




• the remaining elements set b which is the set of elements still to be placed

Inside the recursion, a loop places the N(i) (with i recursion index and) remaining elements producing the same amount of new root sequences and a new recursion is started so that N(i+1)=N(i)-1 hence meaning the overall complexity is O(N!) as expected

The recursion ends when there are no more elements to place hence b.empty() is true

Each recursion set ends with a valid sequence hence they are all merged together in a final list of sequences

Here is my CPP solution

#include <iostream>
#include <vector>
using namespace std;

vector<int> remove_item (const vector<int>& a, const unsigned int id)

 vector<int> res; 
 for(unsigned int i=0; i<a.size(); ++i) if(i!=id) res.push_back(a[i]); 
 return res;



vector<int> add_item(const vector<int>& a, const int b)

 vector<int> res=a; 
 res.push_back(b); 
 return res;


vector< vector<int> > merge(const vector< vector<int> >& a, const vector< vector<int> >& b)

 vector< vector<int> > res=a; 
 for(const auto& e : b) res.push_back(e); 
 return res;




vector< vector<int> > permutations(const vector<int>& b, const vector<int>& a=)


 if(b.empty()) return a ; 

 vector< vector<int> > res; 
 for(unsigned int i=0; i<b.size(); ++i) res=merge(res, permutations(remove_item(b,i), add_item(a, b[i]))); 
 return res; 


int main() 
 // your code goes here

 auto res = permutations(1,2,3,4,5); 
 cout << "Sol Num = " << res.size() << endl; 
 for(const auto& a : res) 
 
 for(const auto& b : a) cout << to_string(b) << " "; 
 cout << endl; 
 
 return 0;

A cleaner solution is to trust the standard library and try to re-use the generic components already available there. Your problem is solved by std::next_permutation, so you can proceed along the lines of:

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

int main()

 std::vector<int> v = 1, 2, 3, 4, 5 ;

 do
 
 for (auto e : v)
 std::cout << e << " ";
 std::cout << "n";
 
 while (std::next_permutation(v.begin(), v.end()));

For pedagogical purposes, if you wanted to keep your current structure, you could also use standard functions there. In particular, remove_item and merge could be rewritten to:

std::vector<int> remove_item(const std::vector<int>& a, int id)

 assert(id >= 0 && id < a.size());

 std::vector<int> res(a.begin(), a.begin() + id);
 res.insert(res.end(), a.begin() + id + 1, a.end());
 return res;


std::vector<std::vector<int> > merge(const std::vector<std::vector<int> >& a, const std::vector<std::vector<int> >& b)

 std::vector<std::vector<int> > res(a);
 std::copy(b.begin(), b.end(), std::back_inserter(res));
 return res;

Whatever you do, as general comments:

• Avoid writing using namespace std;.




• Don't write std::endl when n will do.




• You don't need std::to_string, just print b.



• 
  

  You are more likely to make mistakes when you put multiple statements on the same line. So instead of writing for(...) if(...) v.push_back(x); just write

  
  
  

  for(...)
  
   if(...)
   
   v.push_back(x);
   
  
  

  
  
  

  This also improves readability.

  
  

I understand the need to reinvent the wheel but in this case you reinvented an other kind of wheel: functional-style combinatorics aren't very well suited to C++ and the high-performance / low-memory usage it is well known for. I mean, that's a bike wheel for a car.

Now if you want to reinvent the C++ wheel, the best thing would be to re-implement std::next_permutation: an algorithm that does its work incrementally, in place, and with iterators (meaning that you can compute the permutations of strings, arrays, double-linked lists and everything that exposes bidirectional iterators).

Interestingly, there's an example of implementation on cppreference.com:

template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)

 if (first == last) return false;
 BidirIt i = last;
 if (first == --i) return false;

 while (true) 
 BidirIt i1, i2;

 i1 = i;
 if (*--i < *i1) 
 i2 = last;
 while (!(*i < *--i2))
 ;
 std::iter_swap(i, i2);
 std::reverse(i1, last);
 return true;
 
 if (i == first) 
 std::reverse(first, last);
 return false;
 
 

This implementation is a good example of "C++-sprinkled" C code. It's rather elegant but difficult to understand. If you reverse-engineer it though, you'll see it's quite simple:

• first, beginning from the end, find the first adjacent items in increasing order. Let's call the lesser item's position the permutation point. If there are none, that was the last permutation: reverse and return false;




• then, also beginning from the end, find the first item whose value is superior to that of the permutation point. Swap those two, reverse the range (permutation_point, last) and return true.

Now we're ready to reinvent a C++ wheel the C++ way:

#include <algorithm>
#include <iterator>

template <typename Iterator>
bool permute(Iterator first, Iterator last) std::next(first) == last) return false;

 // first step: first adjacent elements in increasing order, starting from the end
 const auto r_first = std::reverse_iterator(last);
 const auto r_last = std::reverse_iterator(first);
 auto position = std::adjacent_find(r_first, r_last, [](auto lhs, auto rhs) 
 return lhs > rhs;
 );
 // check if it was the last permutation
 if (position == r_last) 
 std::reverse(first, last);
 return false;
 
 ++position; // advance position to the lesser item

 // second step: swap the permutation point and the first greater value from the end
 std::iter_swap(position, std::find_if(r_first, position, [position](auto value) 
 return value > *position;
 ));
 std::reverse(r_first, position);
 return true;