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?

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.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