k-th Permutation of [1..n] (Factorial Number System)
Problem statement
Given integers n and k, return the k-th permutation (1-indexed, in lexicographic order) of the sequence [1, 2, ..., n], as a list.
There are n! permutations ordered lexicographically; k = 1 is [1, 2, ..., n] and k = n! is [n, n-1, ..., 1]. You are guaranteed 1 <= k <= n!.
Complete:
kth_permutation(n: int, k: int) -> List[int]
Example: n = 3, k = 3. The order is [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1], so the 3rd is [2,1,3].
Show hint
How many permutations share the same first element, and how does lexicographic order group them?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.