This challenge is to calculate the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Thinking back to my math classes in high school, I remembered that the maximum number of permutations possible for a given number can be calculated by n!. Knowing this, you can calculate any permutation value you want quickly without brute force. To figure out the first number, we need to calculate how many times we need to permutate 9!. 9! = 362880, so we know the first 362880 numbers start with 0, 362881 - 725760 start with 1, and 725761 - 1088640 start with 2. Because 1088640 is greater than the number we're attempting to look for, we know the first number in the answer has to be 2. Because we only know for sure that the 725761th permutation is 2013456789, we know we're 1000000 - 725761 or 274239 permutations away from the answer. We can keep using this method to narrow down to the final answer.

Program.cs
using Common.Math; using System; using System.Collections.Generic; namespace ProjectEuler_24 { internal class Program { private static void Main(string[] args) { ListFactorial CodepermNumbers = new List { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int[] answer = new int[10]; // the number of permutations remaining is 1 less than the number we are // looking for because the first perumation is our starting point int permutationsRemaining = 999999; int answerIdx = 0; for (int i = 1; i < 10; i++) { // because the most permutations possible is described as n! // we want to figure out how many times we have to go through, // this gives us the first number int factorialVal = (10 - i).Factorial(); int x = permutationsRemaining / factorialVal; // now we need to calculate how many permutations remain after // we set the first number to continue narrowing down our calculation permutationsRemaining = permutationsRemaining % factorialVal; // set the answer then increment the index answer[answerIdx++] = permNumbers[x]; // can't use the number again, remove it permNumbers.RemoveAt(x); // make sure we haven't already calculated the permuation value // we're trying to get if (permutationsRemaining == 0) { break; } } Console.WriteLine($"The 1000000th lexicographic permutation is: {string.Join("", answer)}"); } } }

public static int Factorial(this int num) { if (num < 0) { return 0; } int result = 1; for (int i = 1; i <= num; i++) { result *= i; } return result; }

The Factorial extension I've added to my common math library from the previous post. I've only posted the code to generate it rather than the full class since it's the only portion relevant.

Recent Blog Activity

Blog Archive

© 2016 - 2022 - Justin Sommercorn