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:

// 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:

[ 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:

[ 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:

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!

No tags

The last time I presented a method to generate a random permutation of a given list, in linear time, based on another article.

The problem with that approach is that the algorithm used does not provide a uniform distribution of the resulting lists, for a number of reasons. Actually, call the set of the permutations of the input list, the function randPermutateArray is not even surjective! This can easily be verified by noting that the function will always swap the element of index i by another one, of index between 0 and i-1, and thus the last element will always be displaced.

Although this can be desired for some applications, it is definitely not what I need.

A linear, unformly distributed random list permutation algorithm

A function with the desired properties (surjective, uniformly distributed permutations, linear complexity) would be like constructing a list with elements randomly extracted from a source set. The easiest way to achieve this is to use the input array (size n) as the source set, randomly select an index (from 0 up to the last one) and swap it with the last element, and then loop this considering an array of size n-1:

let randPermuteArray a =

    let n = Array.length a

    let rec aux = function

        | 0 -> a

        | k ->

            let i = rand(k+1)

            let tmp = a.[i]

            a.[i] <- a.[k]

            a.[k] <- tmp

            aux (k-1)

    aux (n-1)

As you can see, the key difference is the random index we select. With this approach, every permutation of the input sequence (the input sequence itself as well!) is as likely to be yielded as the others.

At least if your randomness source is really random… but that’s for another article!

No tags

Hello!

I was working on a F# project doing some maths, and I needed a time-efficient way to generate random permutations of the list [0; 1; ...; n ], for a positive integer n.

First attempt

My first attempt was very naive, poor in performance. It’s complexity was O(n²).

Start with a random integer generator:

let rand =

    let rndGen = new System.Random(int System.DateTime.Now.Ticks)

    (fun max -> rndGen.Next(max))

The idea was to randomly extract elements from a “source” and use them to construct the list. The code looks like this:

let randUniqueIntList max =

    let rec aux l s =

        match List.length s with

        | 0 -> l

        | n ->

            let i = rand(n)

            let r = s.[i]

            aux (r::l) (List.filter (fun x -> x <> r) s)

    let l0 = [0 .. (max - 1)]

    aux [] l0

The recursive aux function takes an accumulator list and a source list. It is recursively called roughly max times. The bottleneck in each run of aux is clearly the call to List.filter, which is O(List.length s) in complexity. Therefore, the overall complexity of this function is O(n²)!

More efficient solution

In this thread at hubFS, I was pointed to an article showing an efficient function that randomly permutes an array (using the fact that an array is a mutable structure), as follows:

let randPermutateArray a =

    let n = Array.length a

    for x in 1 .. n do

        let i = n - x

        let j = rand(i)

        let tmp = a.[i]

        a.[i] <- a.[j]

        a.[j] <- tmp

    a

Since I wanted to work only with immutable data in my code, I wrapped that function around another one in order to encapsulate the mutable array, as follows:

let randPermutateList l =

    let a = Array.of_list l

    a |> randPermutateArray |> List.of_array

Voilà, a function to randomly permutate a generic list with O(n) complexity!

To generate the random permutation of [ 0 .. n ], the code is straightforward:

let genRandomIntList n =

    [ 0 .. n ] |> randPermutateList

Can you further improve the algorithm on performance? Comment on it!

No tags