Iterative version of a permutations algorithm

Question

For learning purposes, I've written an iterative version of a recursive algorithm for generating the set of permutations for a given set of unique integers.

Can I make any improvements to increase readability and performance?

I've also read in various sources that when transforming a recursive algorithm into an iterative one, the stack data-structure is often used to 'substitute' the call stack used in the recursive case. I'm not using a std::stack here but could I have used one to simplify my implementation?

using std::vector; vector<vector<int>> permutations(vector<int> integers) { vector<vector<int>> curr_perms; if (integers.size() <= 1) { curr_perms.push_back(integers); return curr_perms; } size_t sz = integers.size(); vector<vector<int>> next_perms; // initialise with the one permutation of the last single element vector<int> t = { integers[sz - 1] }; curr_perms.emplace_back(t); // backwards iterating a sequence of at least two elements for (int i = sz - 2; i >= 0; --i) { auto first = integers[i]; for (const auto &s : curr_perms) { for (auto j = 0U; j < s.size() + 1; ++j) { vector<int> p(s.begin(), s.end()); // make a copy p.insert(p.begin() + j, first); // shuffle in 'first' element next_perms.push_back(std::move(p)); // and add this as a new permutation } } // permutations found in this iteration are the input for the next std::swap(next_perms, curr_perms); // <-- is this needlessly copying all the elements? next_perms.clear(); } return curr_perms; } 

Answer 1

As often, the recursive algorithm is readable and beautiful, but not very efficient: stack consumption can be overwhelming, memory allocations are plentiful, and you're forced to compute the whole set of permutations at once.

When you mechanically translate the recursive algorithm into its iterative form, you often lose most of its beauty and readability, without gaining much on the front of performance: you just emulate with a data structure what the compiler would have done. It might be useful sometimes but you can generally assume that the compiler will do a better job than yourself.

Hence I would recommend looking into two alternative approaches:

• the first is to do it the standard library way, and provide a std::next_permutation function which return the next permutation in the lexicographical order (see for instance my answer to this question). It can be improved upon though, with the SJT algorithm, and that would be an exercise of choice;

• the second is to keep the general, incremental reasoning of the recursive algorithm, but use the additional knowledge you get in the iterative form: indeed, on the contrary to the recursive form, you know upfront how many permutations you'll return in the end, and thus can avoid all but one allocation.

For instance:

#include <vector> std::vector<std::vector<int>> permutations_set(const std::vector<int>& set) { if (set.empty()) return {}; auto current = std::begin(set); // the unique memory allocation std::vector<std::vector<int>> permutations(factorial(set.size()), {*current}); for (++current; current != std::end(set); ++current) { std::size_t offset = 0; // offset plays the central role here; you could say it replaces the stack for (auto& permutation : permutations) { const auto initial_size = permutation.size(); permutation.insert(std::next(std::begin(permutation), offset), *current); if (offset++ == initial_size) offset = 0; } } return permutations; }