Project Euler – Problem 24 Solution

Problem

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 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 borrowed the first two functions which are responsible for generating all the permutations of a given list here. From there, I wrote the getLexicographic function which takes an int list, generates all permutations of the numbers in the list, and for each permutation work out its numeric value, 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 sorted numeric values as a list.

To get to the answer, I simply return the millionth element in the list.