# Project Euler Problem 24

Project Euler Problem 24 requires the only specific piece of math information that number of all permutations of n items is n! (factorial n).

Now imagine we put 0 to the most left place; the number of all permutations with 0 tied at this position is factorial 9, or 362880. So the 1000000th lex ordered permutation is going to be somewhere in a group beginning with digit 2. Specifically, in this group of permutation, beginning with 2, it would be 1000000 – 2*(9!) = 274240th permutation. Selecting permutations now from group of 9 items [0;1;3;4;5;6;7;8;9] this gives us second digit as 7 (274240 – 6*(8!) = 32320th of permutations from 8 items [0;1;3;4;5;6;8;9] that are prepended with “27”. Etc…

open System let fact n = [1..n] |> Seq.reduce (*) let exclude elem = set >> Set.remove elem >> Set.toArray let lexPermutation nth (digits: int []) = if nth < 1 || nth > fact (digits.Length) then failwith "Permutation # is out of valid range" let rec permutator acc permutationsLeft (members: int []) = if members.Length = 1 then members.[0] :: acc |> List.rev |> List.toArray else let divider = fact (members.Length) / members.Length let idx = permutationsLeft / divider let next = members.[idx] permutator (next::acc) (permutationsLeft - divider*idx) (exclude next members) permutator [] (nth - 1) digits // first permutation is 0th, indeed let problem024 () = lexPermutation 1000000 [|0..9|] |> Array.map string |> fun x -> String.Join("", x)

Advertisements

Leave a Comment