K-th Permutation and Rank

Factorial number system: pick digit at each position by dividing remaining rank by (n-1)!.

Try this in Python

import math

def kth_permutation(n, k):
    nums = list(range(1, n + 1))
    k -= 1
    out = []
    for i in range(n, 0, -1):
        f = math.factorial(i - 1)
        idx = k // f
        k %= f
        out.append(nums.pop(idx))
    return out

print(kth_permutation(4, 9))

Key takeaways

• LeetCode uses 1-based k often—subtract 1 for 0-based ranks.
• Duplicate elements need multiset counts in each step.
• Inverse problem: rank from permutation uses same factorials.