Skip to content

Project Euler Problem 24

November 17, 2011

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

From → Project Euler

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: