Project Euler — Problem 24 Solution

Problem

A per­mu­ta­tion is an ordered arrange­ment of objects. For exam­ple, 3124 is one pos­si­ble per­mu­ta­tion of the dig­its 1, 2, 3 and 4. If all of the per­mu­ta­tions are list­ed numer­i­cal­ly or alpha­bet­i­cal­ly, we call it lex­i­co­graph­ic order. The lex­i­co­graph­ic per­mu­ta­tions of 0, 1 and 2 are:

012   021   102   120   201   210

What is the mil­lionth lex­i­co­graph­ic per­mu­ta­tion of the dig­its 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Solution

let rec distribute e = function
    | [] -> [[e]]
    | x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]

let rec permute = function
    | [] -> [[]]
    | e::xs -> List.collect (distribute e) (permute xs)

let getLexicographic (list:bigint list) =
    list
    |> permute
    |> List.map (fun l -> l |> List.rev |> List.mapi (fun i e -> e * pown 10I i) |> List.sum)
    |> List.sort

let answer = List.nth (getLexicographic [0I..9I]) (1000000-1)

I bor­rowed the first two func­tions which are respon­si­ble for gen­er­at­ing all the per­mu­ta­tions of a giv­en list here. From there, I wrote the getLex­i­co­graph­ic func­tion which takes an int list, gen­er­ates all per­mu­ta­tions of the num­bers in the list, and for each per­mu­ta­tion work out its numer­ic val­ue, i.e.

[0; 1; 2] –> [2; 1; 0] –> 2 * (10 POW 0) + 1 * (10 POW 1) + 0 * (10 POW 2) –> 2 + 10 + 0 –> 12

and then returns the sort­ed numer­ic val­ues as a list.

To get to the answer, I sim­ply return the mil­lionth ele­ment in the list.