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

No comments yet.

<< An old JavaScript implementation bug – parseInt

Generating random int list in F# >>