Compute all the permutations for a given vector of integers

Question

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

Answer 1

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.

Answer 2

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) {
    // check if there are at least two elements
    if (first == 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;
}