Hello!

This is one of my first attempts on F# (and with functional programming). Any suggestions are welcome.

In a math application I'm writing, I need to generate many random permutations of the list [ 0 .. n ], for a given positive integer n.

My first attempt was to write a generic random integer generator using a closure (I think this is what you guys usually do -- if not, please tell me!), and then my random list<int> generator like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

let rand =
    let rndGen = new System.Random(int System.DateTime.Now.Ticks)
    (fun max -> rndGen.Next(max))

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

This evidently works, however naive it may look. My idea was to have a "source" of numbers and then randomly extract one by one and construct a list from it. The source is then the list l0, and the function responsible for this extraction is the nested function "aux".

The problem with this is that it is way too slow, ie, O(max^2). (rapidly analyzing this routine, the loop will execute "max" times, but the item removing part (the "filter") has complexity O(n) ==> the whole thing: O(max^2)).

I looked for another structure for my "source" without success. (I tried playing with Set and Hashtbl from the PowerPack).

The other possibilities would be to look for another algorithm. I tried, but the ones I found were either worse (in time complexity) or unable to produce every random permutation possible (so they were (highly) biased).

Do you have any suggestions on how to improve this algorithm?

Thanks a lot!
Bruno

ps: is there a way to make the forum autoformat the F# code I type? (edit: Thanks, brianmcn!)