## 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:

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

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