# The nth permutation of a sequence of symbols in F#

Project Euler‘s problem 24 deals with permutation of symbols.

More specifically, given the initial sequence of symbols (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), it asks its 1.000.000th lexicographic permutation.

The nth lexicographic permutation of a sequence of symbols is defined as the nth element of the lexicographically ordered set of permutations of that symbols.

To help clarify this definition, take for example the symbols (a, b, c). The lexicographically ordered set of permutations is computed by determining all the permutations, and then sorting them according to the lexicographical order (a.k.a. alphabetical order):

1. abc
2. acb
3. bac
4. bca
5. cab
6. cba

So, in this case, the 4th lexicograph permutation of (a, b, c) is “bca”.

A solution to the initial problem is then rather simple to construct in very naive way: list all the (10! = 3628800) permutations, sort them all, and take the 1.000.000th. However this may take a lot of memory and time. And most importantly, for any given sequence of symbols, it can be done in O(1).

The constant-complexity algorithm is rather simple and can be easily implemented in F# as follows:

This algorithm might be much more powerful than what is needed to solve problem 24, but it is much more generic in nature.

Indeed, it does not generate only lexicographically ordered permutations. The permutationsare generated in an order defined by that of the input sequence. So, let’s say you wanted the 1.000.000th reverse-lexicographic order, you would obtain it as follows:

If you would like the 15th permutation of the sequence (a, 1, b, 2, f, z, 3), you could do:

Finally, this algorithm provides an easy way to obtain random permutations. Simply generate a random integer to be used as the permutation index:

That’s it! I hope this can be useful to someone!

## One ResponseLeave one →

1. #### annu

/  2010-09-01

I want to whole symbols deatil of advanced calculus.

Reply