brunoreis.com/tech

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!