Problem

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?

Answer

2783915460

Python

#!/usr/bin/env python
from itertools import islice, permutations
print(''.join(next(islice(permutations(list(map(str, list(range(10))))), 999999, None))))

Ruby

#!/usr/bin/env ruby
puts (0..9).to_a.permutation(10).to_a[999999].join

Haskell

import Data.List (sort, permutations)

main :: IO ()
main = putStrLn $ (sort $ permutations ['0'..'9']) !! 999999

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(""))

Mathematica

(* 
 * We generate all 10! permutations of the sequence (0,1,2,3,4,5,6,7,8,9)
 * into memory, and select the 1 000 000th element (1-based indexing).
 *)
FromDigits[Permutations[Range[0, 9]][[1000000]]]

Java

public final class p024 implements EulerSolution {
	
	public static void main(String[] args) {
		System.out.println(new p024().run());
	}
	
	
	/* 
	 * We initialize an array as the lowest permutation of the given digits, which is the sequence
	 * (0,1,2,3,4,5,6,7,8,9). Then we call the next permutation algorithm on it 999 999 times
	 * (because the index in the problem is 1-based), and stringify the resulting sequence.
	 * 
	 * The next permutation algorithm is well-known and a bit long to explain.
	 * See: https://www.nayuki.io/page/next-lexicographical-permutation-algorithm
	 */
	
	public String run() {
		// Initialize
		int[] array = new int[10];
		for (int i = 0; i < array.length; i++)
			array[i] = i;
		
		// Permute
		for (int i = 0; i < 999999; i++) {
			if (!Library.nextPermutation(array))
				throw new AssertionError();
		}
		
		// Format output
		String ans = "";
		for (int i = 0; i < array.length; i++)
			ans += array[i];
		return ans;
	}
	
}