MathJax

SyntaxHighlighter

Highlight

Custom CSS

Saturday, January 23, 2010

Project Euler #24: Lexicographic permutations

Here is the question:

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?

Only an elementary understanding of combinatorics is required to solve this problem by hand. Start with the smallest possible digit (0 in this case), then find the number of permutations of the remaining digits. If this number is less than 1000000, then 0 cannot be the first digit in the 1000000th permutation.

Try 1 instead, and count the number of permutations. Keep going with 2, 3, 4, etc until the number of permutations exceeds 1000000. Suppose that fixing the first digit at $$k$$ results in more than 1000000 permutations; this means the first digit is fixed at $$k-1$$, and the second digit must be examined by this method.

A diligent Project Euler enthusiast can execute this method by hand, but here is a simple program written in Scala that demonstrates this method:

val digits = List(0,1,2,3,4,5,6,7,8,9)
val target = 1000000

def fact(n: Int): Int = {
  def recur(n: Int, acc: Int): Int = if (n == 1) acc else recur(n-1, n*acc)
  if (n == 0) 1 else recur(n, 1)
}

def compute(list: List[Int]): List[Int] = {
  def recur(list: List[Int], current: Int): List[Int] = {
    val permutations = fact(list.length - 1)
    val index = (target - current) / permutations
    val digit = list(index)
    val next = current + index * permutations
    list.length match {
      case 2 if target - current == 0 => list
      case 2 if target - current == 1 => list.reverse
      case _                          => digit :: recur(list - digit, next)
    }
  }
  recur(list, 1)
}

val result = compute(digits).mkString("")
println(result)
Post a Comment