# Sorted permutations

Published on 2011-07-28The next problem in Project Euler asks for the 1,000,000^{th} permutation (sorted smallest to largest) of 0123456789. It reads:

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:

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

There are 10! possible permutations, and 10! isn't much greater than 3.5 million, so brute force wouldn't be out of the question: one could declare a list of integers, add every possible permutation to the list, sort it, then return the 1,000,000^{th} member of the list, but that didn't feel very sporting. I thought a smarter/faster way to compute the requested permutation would be to calculate it digit by digit.

Because the number of possible permutations is equal to the factorial of the number of digits, one can think of the permutations as a number expressed in, for lack of a better term, base factorial. 10! is 10 × 9!, meaning that in an ordered list of all permutations of 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9, permutations 1 - 9! must start with a zero, permutations 9! + 1 through 9! × 2 must start with 1, permutations 9! × 2 + 1 through 9! × 3 must start with 3, and so on. Since we're looking for the 1,000,000^{th} permutation, we know that it must start with 1,000,000 / 9!, or 2. We can repeat this process for every digit, modifying a list of remaining digits to make sure there are no repeats.

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Problem024 { class Program { static void Main(string[] args) { int[] digits = new int[10]; int factorial; int remainder = 999999; List<int> remainingDigits = new List<int>(); for (int i = 0; i < 10; i++) remainingDigits.Add(i); for (int i = 0; i < 10; i++) { if (remainder == 0) { digits[i] = remainingDigits[0]; remainingDigits.Remove(digits[i]); continue; } factorial = factorialize(9 - i); digits[i] = remainingDigits[(remainder / factorial)]; remainingDigits.Remove(digits[i]); remainder %= factorial; } foreach (int n in digits) Console.Write(n); Console.Write('\n'); } private static int factorialize(int p) { if (p == 0) return 1; int factorial = p; for (int i = 1; i < p; i++) factorial *= i; return factorial; } } }