## Another (iterative) technique for enumerating permutations

The idea of writing this post came up by reading Programming Interview Questions 11: All Permutations of String by Arden Dertat. The author proposes a simple and elegant recursive algorithm that finds all the permutations of a given string.

If any of you is interested in an alternative (iterative) solution, here is one. I think it has a couple of features you may find interesting.

The starting point is to define an order among all the permutations and then write a procedure that, given a permutation, returns the following one. The order is simply the lexicographic order and the procedure is the following.

- Let
`p[0..n-1]`

be the current permutation, having size`n`

- Find the last
`k > 0`

for which`p[k] > p[k-1]`

; if this element does not exist, let`k = 0`

- Reverse
`[k, n-1]`

- If
`k != 0`

, swap`p[k-1]`

with the smallest element`p[s]`

in`[k, n-1]`

for which`p[k-1] > p[s]`

Here is a C++ implementation of the procedure. I chose C++ over Java because I wanted to make it
generic enough to accept both a `string`

and a `vector`

.
Actually, you can pass it anything that supports the `[]`

operator, has a
`size_t size()`

method and which elements can be compared with `>`

.

If you want, you can easily refactor this function to make it accept a comparator (as a function object).

#include <algorithm> /** * @brief This function, given a permutation, transforms it into the next * one in lexicographic order. * * @tparam Container Any type of container, provided it supports the * `[]` operator, has a `size_t size()` method and the * elements stored within support the `>` operator * * @param p The current permutation. This function will * transform it into the next one in lexicographic * order. * * @return `false` if the last permutation (e.g. `ZYXW...DCBA`) * was provided as input, `true` otherwise. * If the function returned false, then `p` has been * transformed into the first permutation * (e.g. `ABCD...WXYZ`). */ template<typename Container> bool next_permutation(Container& p) { const size_t n = p.size(); size_t k = 0; for (size_t i = 1; i < n; i++) { if (p[i] > p[i-1]) k = i; } std::reverse(p.begin() + k, p.end()); if (k != 0) { size_t s = k; while (s < n) { if (p[s] > p[k-1]) break; s++; } std::swap(p[k-1], p[s]); return true; } // reached last permutation return false; }

The function returns `false`

if the last permutation was provided as input,
`true`

otherwise. Usage example:

std::string str = "ABCDE"; do { std::cout << str << std::endl; } while (next_permutation(str));

Therefore, to get all the possible permutations as a `std::vector`

you can use the
following convenience function:

template<typename Container> std::vector<Container> get_all_permutations(Container p) { std::vector<Container> result; // Due to how next_permutation works, sorting the items in p // is necessary if we want to fetch all the permutations std::sort(p.begin(), p.end()); do { result.push_back(p); } while (next_permutation(p)); return result; }

This solution is actually much less powerful than the ones based on factorial numbering systems and much less concise (or elegant) than the ones using recursion. However it has at least two useful features:

- It gracefully handles strings containing repeated letters. For example, if you
provide
`LEVEL`

as input to`get_all_permutations()`

, the function will return all the 30 (5!/(2!2!)) possible anagrams of the word`LEVEL`

, in lexicographic order and without listing two times permutations like`ELLEV`

and`ELLEV`

where the two identical`E`

’s are just exchanged. - The enumeration can be easily stopped and resumed. Provided you don’t use
`get_all_permutations()`

you can call`next_permutation()`

`k`

times, store the last permutation (p_{k+1}) and later on you can continue fetching permutations starting from p_{k+1}.

This is just a random idea. The code has not been thoroughly tested, and I think you can find solutions which are better than this just around the corner.

**UPDATE**: I’ve discovered that the C++ standard library has a function named
`next_permutation`

that probabily applies a similar algorithm. Moreover,
many other people propose almost identical solutions to get the next permutation,
in many different languages.

I’ve just reinvented the wheel but it was fun! :)