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:
*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 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 [] l0The recursive

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 aSince 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_arrayVoilà, 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 ] |> randPermutateListCan you further improve the algorithm on performance? Comment on it!