Lexicographic permutations

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?

---

Idea

Observation:

• 10 digits permutation has factorial(10) = 3628800 kinds, 9 digits permutation has factorial(9) = 362880 kinds
• starting with 0 and 1 could take up 2 * factorial(9) permutations, remaining factorial(10) - 2 * factorial(9) to fulfill
• inspired by this, we could alwasy calculate how many permutations has been fulfilled and how many need to fulfill

ATTENTION : used digits need to remove to avoid duplication, which conflicts with 'permutation'

---

from math import factorial

list(map(factorial, range(1, 11)))

[1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]

def solve(ith):
    digits = list(range(10))
    permutation = []
    for i in range(10):
        d = ith // factorial(9-i)
        ith %= factorial(9-i)
        permutation.append(digits[d])
        digits.pop(d)
    return ''.join(map(str, permutation))

solve(int(1e6)-1)

'2783915460'