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.