Lexicographic Permutations

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:

\begin{align} 012, 021, 102, 120, 201, 210 \end{align}

What is the millionth lexicographic permutation of the digits \(0, 1, 2, 3, 4, 5, 6, 7, 8\) and \(9\)?

Solution

Scala’s standard library is so good that this problem can be solved in just a single line. The .permutations create permutations, already in lexicographic order, so we just need to find the millionth one.

object Euler024 extends EulerApp {
  override def execute(): String = "0123456789".permutations.drop(999_999).next()
}

It’s all Iterator-based, which means that there’s no need to store all the million permutations in the memory. Perfectly readable and efficient. I wish all problems could be solved like that!