Project Euler Problem 024

Statement

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?

Solution

For this problem we need to find the 999999th element of a 10 element permutation if
using 0-index based.
With 9 elements we have 362880 combinations, so for each 362880 combinations we change
the first digit. So: 999999 / 362880 = 2 -> so we pick the digit in position 2(0-based index) from
the list of digits place it as first digit of the result and remove it from the list.
Then we have to find the 999999 mod 362880 = 274239th combination from 8 element permutations

We follow the same technique applied for the first case, this can be done easily with pencil and paper
but like we are programming let's do it in Python:

from CommonFunctions import factorial
 
def combinations(n, r):
    return factorial(n) // (factorial(n - r))
 
if __name__ == '__main__':
    number = 999999
    lst = list(range(10))
    result = []
    for i in range(9, -1, -1):
        comb = combinations(i, i)
        index = number // comb
        number = number % comb
        result.append(str(lst.pop(index)))
    print("The result is:", ''.join(result))

The Python file is available for download here.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License