Problem 24: What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Completing this one marks my advance to “level 1”, having completed 25 problems (I completed Problem 67 when I completed Problem 18), and placing me in the “above what 80.11% of members have failed to do” category.

The algorithm itself was learned from http://stackoverflow.com/questions/352203/generating-permutations-lazily, which produces permutations lexicographically in sequence.  Of course, the example given there is in C++, so my F# solution is much different.  My first attempt was horrid.  After several iterations I finally got it to perform well (about 90 milliseconds, from about 6 seconds) and to at least look kind of functional.

let problem24g =
    let advance (perm:int[]) =
        //Find the longest "tail" that is ordered in decreasing order ((s+1)..perm.Length-1).
        let rec find i =
            if perm.[i] >= perm.[i-1] then i-1
            else find (i-1)
        let s = find (perm.Length-1)
        let s' = perm.[s]
        
        //Change the number just before the tail (s') to the smallest number bigger than it in the tail (perm.[t]).
        let rec find i imin =
            if i = perm.Length then imin
            elif perm.[i] > s' && perm.[i] < perm.[imin] then find (i+1) i
            else find (i+1) imin
        let t = find (s+1) (s+1)
        
        perm.[s] <- perm.[t]
        perm.[t] <- s'
        
        //Sort the tail in increasing order.
        System.Array.Sort(perm, s+1, perm.Length - s - 1)
    
    let perm = [|0;1;2;3;4;5;6;7;8;9|]
    let rec find i =
        if i = 1000000 then perm
        else advance perm ; find (i+1) 
    find  1