cplusplus.co.il

Enumerating permutations

Posted on: 14/11/2009

There are exactly n! different permutations of n numbers. This challenge was about writing a function which is able to enumerate all these permutations, i.e. function permute(n, idx) which is able to return permutation with index idx of n numbers. The requirement is ofcourse that all these permutations must be unique – this is in order to go over all possible permutations.

Here’s my solution to this problem, along with a test program:

#include <set>
#include <string>
#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>

// ---- generate permutation according to idx ----

std::vector<unsigned> permute (unsigned n, unsigned idx) {
    std::vector<unsigned> res(n);
    // I would love idx to be 1-based:
    idx += 1;
    // init the vector such that res[i]=i
    for (size_t i=0;i<res.size();++i)
        res[i] = i;
    // now lets create the permutation
    for (unsigned curr=0;curr<res.size();++curr) {
        std::swap(res[n-1-curr], res[idx % (n-curr)]);
        idx /= n-curr;
    }
    return res;
}

// ---- auxiliary, computes a factorial in compile time ----

template <unsigned N>
struct fact {
    static const unsigned result = N * fact<N-1>::result;
};

template <>
struct fact<0> {
    static const unsigned result = 1;
};

// ---- test program ----

int main () {
    const unsigned n = 5; // size we're checking

    std::set<std::vector<unsigned> > s;
    for (unsigned i=fact<n>::result;i;--i) {
        // compute current permutation
        std::vector<unsigned> v = permute(n, i);
        // print it
        std::copy(v.begin(), v.end(),
            std::ostream_iterator<unsigned>(std::cout, " "));
        std::cout << std::endl;
        // verify uniqueness:
        if (s.find(v) != s.end()) {
            std::cout << "Dupe!" << std::endl;
            return 1;
        }
        s.insert(v);
    }
}
Advertisements

5 Responses to "Enumerating permutations"

Nice solution!

I have to say though, the challenge on my blog wasn’t exactly about enumerating permutations.
The goal in the challenge was to generate a single, specific permutation, in such a way that all permutations of a given sequence may be generated.

This is a subtle difference – consider the goal of shuffling a sequence of elements. (The “standard” way of doing this is decorating with random, sorting, and then undecorating, but let’s ignore that for a second.)
Using the solution to this challenge and given a random number in the range 1..n!, you could permute the sequence according to that number. Having the solution work in almost O(n) and not going over all “previous” permutations allows this shuffling to be efficient.

Generating a random permutation (shuffling) does not require sorting etc, it can be achieved in a manner like this:

vector<unsigned> v(n);
for (size_t i=0;i<v.size();++i)
  v[i] = i;
for (size_t curr=0;curr<v.size;++curr)
  std::swap(v[n-1-curr], v[rand(0, n-1-curr)]);

(Assuming rand(x,y) returns an unsigned integer between x and y, inclusive)

This one was hard for me because I had to somehow generate all the random values from the single idx parameter, which took some time to get right.

Thanks for the feedback. I really enjoyed the challenge!

You’re welcome, I’m happy that this challenge generated this interest, and many people tried it. By the way, another nice challenge I think you’ll like is generating random numbers according to a given (bell shaped) function, which I gave on my blog here:
http://www.algorithm.co.il/blogs/index.php/programming/python/small-python-challenge-no-3-random-selection/

One of my next posts will explain some nice mathematical concepts that lie behind the common solution to this challenge. I hope it will be educating as well as interesting.

By “this challenge” that a next post will explain I meant the permutation generation challenge 🙂

By the way, the standard algorithm next_permutation does something pretty similar. It is thoroughly described (along with implementation) here.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: