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):
- abc
- acb
- bac
- bca
- cab
- 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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// You can use your own factorial
// factorial : BigInteger -> BigInteger
let factorial n = Seq.fold ( * ) 1I [ 1I .. n ]
let nthPermutation n (symbols:#seq<'S>) =
let symbols = new ResizeArray<'S>(symbols)
let rec aux n acc = function
| sz when sz = 0I -> acc |> List.rev
| sz ->
let sz' = sz - 1I
let k = factorial sz'
let i = n / k
let s = symbols.[int i]
symbols.RemoveAt(int i)
aux (n%k) (s::acc) sz'
aux n [] (BigInteger (symbols.Count))
let problem24 =
[ 0 .. 9 ]
|> nthPermutation 999999I // 0-based index!! |
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:
|
1 |
[ 9 .. -1 .. 0 ] |> nthPermutation 999999I |
If you would like the 15th permutation of the sequence (a, 1, b, 2, f, z, 3), you could do:
|
1 2 3 |
[ box 'a'; box 1; box 'b'; box 2; box 'f'; box 'z';
box 3 ]
|> nthPermutation 14I |
Finally, this algorithm provides an easy way to obtain random permutations. Simply generate a random integer to be used as the permutation index:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
let symbols = [ 0 .. 9 ]
let totalPermutations =
symbols
|> List.length
|> BigInteger
|> factorial
open System
let random = new Random(int DateTime.Now.Ticks)
symbols
|> nthPermutation (BigInteger (random.Next(totalPermutations))) |
That’s it! I hope this can be useful to someone!
annu
/ 2010-09-01I want to whole symbols deatil of advanced calculus.