2013-07-05

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.

  1. Let p[0..n-1] be the current permutation, having size n
  2. Find the last k > 0 for which p[k] > p[k-1]; if this element does not exist, let k = 0
  3. Reverse [k, n-1]
  4. 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:

  1. 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.
  2. 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 (pk+1) and later on you can continue fetching permutations starting from pk+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! :)

Tags: algorithms, cpp
comments powered by Disqus
Fork me on GitHub