Challenge: Lexicographic permutations

Posted on: October 19, 2016 2:12:46 AM
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)
        {
            List permNumbers = 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)}");
        }
    }
}
Factorial Code
        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.

Comments


No comments yet, be the first to leave one.

Leave a Comment