# 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.