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 of course 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); } }

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:

(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.