Iterative version of a permutations algorithm
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 &lt;vector&gt;

std::vector&lt;std::vector&lt;int&gt;&gt; permutations_set(const std::vector&lt;int&gt;&amp; set) {

    if (set.empty()) return {};

    auto current = std::begin(set);

    // the unique memory allocation
    std::vector&lt;std::vector&lt;int&gt;&gt; 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&amp; 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;           
}