Permutation indexing

Factorial base — rank / (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

• 1-based k check.
• Duplicates multiset.
• Rank inverse.