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

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.267s
user   0m3.920s
sys    0m0.347s

## 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 permutations.js real 0m0.080s user 0m0.072s sys 0m0.008s ## 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.034s
user   0m0.025s
sys    0m0.009s

## Ruby

#!/usr/bin/env ruby
puts (0..9).to_a.permutation(10).to_a[999999].join
$time ruby permutations.rb real 0m1.951s user 0m1.864s sys 0m0.087s ## Rust fn permutate<T>(sequence: &mut [T]) -> bool where T: Ord, { if sequence.len() < 2 { return false; } let mut i = sequence.len() - 1; while i > 0 && sequence[i - 1] >= sequence[i] { i -= 1; } if i == 0 { return false; } let mut j = sequence.len() - 1; while j >= i && sequence[j] <= sequence[i - 1] { j -= 1; } sequence.swap(j, i - 1); sequence[i..].reverse(); true } fn main() { let mut digits: Vec<char> = "0123456789".chars().collect(); for _ in 1..1000000 { permutate(&mut digits); } println!("{}", digits.iter().collect::<String>()); } $ rustc -C target-cpu=native -C opt-level=3 -o permutations permutations.rs
\$ time ./permutations
real   0m0.006s
user   0m0.000s
sys    0m0.006s