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

• CiaPan: Not only the time complexity, but also the memory complexity is \$O(n!)\$ – because that's the size of your output. For \$n\$ greater than tiny this may be a serious disadvantage...
• Nicola Bernini: The number of permutations is N! which means eventually you need to store all of them so you need O(N!) memory, unless you are allowed to print them as soon as you discover them
• CiaPan: That's it: unless. You never said they must be delivered all at once. So it's a valid supposition you can find them one by one and utilize (for example: print) iteratively...

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.

• Nicola Bernini: Sure, but using the standard library makes it trivial My goal was to develop a working algo
• Juho: @NicolaBernini Indeed, I hope that nobody is discouraged from reviewing your code beyond my answer.
• Blasco: @NicolaBernini Trust Juho, you will be able to write better algorithms if you learn the standard library.
• Nicola Bernini: @WooWapDaBug I already know it (at least at some extent, there is always room for improvement) but I hope it is clear it was not the point of the exercise
• Mast: @NicolaBernini It wasn't, but now the relevant tag is added so it is.

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

• Nicola Bernini: I understand your point and thanks for sharing it, but I have to do bias disclosure now: I (strongly) favour functional style over imperative (which does not mean I’m a purist, otherwise I would not have used loops, I’m just trying to take the best of both worlds) Certainly it can have a performance cost (depends how smart the compiler is) but I think it is not necessary for me to list the joys functional programming
• papagaga: @NicolaBernini: well, you can always put next_permutation into a functional shell (like you do with insert, push_back, etc. in your helper functions). I also like functional programming a lot, and have tried a few times to adopt functional idioms in C++ but there's always a point where you understand C++ won't ever be Haskell. But yeah, sure!
• Nicola Bernini: This is the strategy I adopt typically for my hybrid functional style, but not in this case as I was trying to reimplement next_permutation but in production code that’s what I tend to do. C++ does not need be Haskell, but some C++ programmer would certainly take benefit from some exposure to Haskell :)