Project Euler - Problem 24

Project Euler problem 24 in F#

 

Problem 24 is defined as:

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?

Algorithm

Before diving into the code, let me explain the algorithm I used. Imagine all possible permutations of digits [0..9] as a gigantic tree structure, where each arc between nodes has a digit associated with it. At the top the root node has ten children, corresponding to digits [0..9]. Each node on the second level of the tree only has nine children, corresponding to the numbers [0..9] but sans the digit used to ‘get to’ that node, which continues until you whittle down the list of available digits until there is only one left. Theorm: For any given node in the tree where there are n digits left to be assigned, there are n! total child nodes. (So in the example, the root node has three digits left to be assigned, and thus there are 3! (6) child nodes under the root.)

 

So you know the root node has 10 children, and each child node has 9! nodes under it. Which if you order them lexographically means that permutations (1 – 9!) start with 0, permutations (9! – 2 * 9!) start with a 1, permutations (2 * 9! – 3 * 9!) start with a 2 and so on. Each so called ‘bucket’ for a given node.

 

So to solve this, given a target permutation index find which ‘bucket’ that belongs in and choose that digit index and recurse.

 

Example

What is the third lexographical permutation of [0..2]?

 

For digits [0; 1; 2] the bucket size is 2! (or 2). So permutations 1-2 start with a ‘0’, permutations 3-4 start with a ‘1’, and permutations 5-6 start with a ‘2’. Since we are looking for permutation 3, we choose bucket 2.

For digits [0;2] the bucket size is 1! (or 1). So the permutation 1 start with a ‘0’ and permutation 2 starts with a ‘2’. Since our ‘bucket index’ is now 1, we choose bucket 1.

For digits [2] we only have one choice, and choose 2.

Translation to F#

The code in F# is a great example of the synergy between functional programming and .Net. To build up the list of digits for the lexographical permutation we have a recursive function that simply adds digits to the end of a list. However, we are also removing items from a list of digits to choose from. To represent that we use a mutable .Net List<int> collection.

 

So we are using both immutable functional list types as well as the mutable .Net list types.

 

#light

open System

open System.Collections.Generic

let rec fact x = if x <= 0 then 1 else x * fact (x - 1)

let rec LexoPermutation (digits:List<int>) target =

    if digits.Count = 1 then

        [digits.[0]]

    else

        let bucketSize = (fact digits.Count) / digits.Count

        let digitToSplitIdx = target / bucketSize

        let digitSplit = digits.[digitToSplitIdx]

        digits.RemoveAt(digitToSplitIdx)

        digitSplit :: (LexoPermutation digits (target - bucketSize * digitToSplitIdx))

    

let digits = new List<int>([0..9])

let result = LexoPermutation digits (1000000 - 1)

printfn "%A" result

 

As always, thanks go out to the fine folks at Project Euler.

Comments

• Anonymous
  March 22, 2008
  PingBack from http://msdnrss.thecoderblogs.com/2008/03/22/project-euler-problem-24/

• Anonymous
  November 18, 2008
  One small thing that should be changed. Due to your wording of, "permutations (1 – 9!) start with 0, permutations (9! – 2 * 9!) start with a 1, permutations (2 * 9! – 3 * 9!) start with a 2 and so on.", it sounds like you're saying permuation 2*9! starts with both a 1 and a two. A simple change could be made saying that the range of numbers starting with a certain digit is (9!n + 1) to (9!(n+1)). It isn't a big problem, but it caused me a lot of confusion.