Tjyylli

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 pedagocical 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.