Project Euler Problem 24 Solution

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\displaystyle 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?

Haskell

import Data.List (sort, permutations)

main :: IO ()
main = putStrLn $ (sort $ permutations ['0'..'9']) !! 999999
$ ghc -O2 -o permutations permutations.hs
$ time ./permutations
real   0m4.962s
user   0m4.400s
sys    0m0.496s

JavaScript

function permutate(n, array) {
  const al = array.length
  for (let i = 0; i < n - 1; i++) {
    let k, l
    for (let j = 0; j < al - 1; j++) {
      if (array[j] < array[j + 1]) {
        k = j
      }
    }
    for (let j = k; j < al; j++) {
      if (array[k] < array[j]) {
        l = j
      }
    }
    let tmp = array[k]
    array[k] = array[l]
    array[l] = tmp
    let begin = k + 1
    let end = al - 1
    while (begin < end) {
      tmp = array[begin]
      array[begin] = array[end]
      array[end] = tmp
      begin += 1
      end -= 1
    }
  }
  return array
}
console.log(permutate(1000000, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]).join(""))
$ time node --use-strict --harmony-destructuring permutations.js
real   0m0.431s
user   0m0.356s
sys    0m0.012s

Python

#!/usr/bin/env python
from itertools import islice, permutations
print(''.join(next(islice(permutations(list(map(str, list(range(10))))), 999999, None))))
$ time python3 permutations.py
real   0m0.037s
user   0m0.036s
sys    0m0.000s

Ruby

#!/usr/bin/env ruby
puts (0..9).to_a.permutation(10).to_a[999999].join
$ time ruby permutations.rb
real   0m2.609s
user   0m2.464s
sys    0m0.124s

Questions? Comments? Send me an email: z@chdenton.com