Use factorial-based indexing. For n items, there are (n-1)! permutations starting with each first element.
Divide k by (n-1)! to find which element goes first. Subtract that block, repeat for remaining elements.
Example: n=4, k=9. (4-1)! = 6. k=9 means skip the first block (index 0) and take index 1 of the second block.
This builds the permutation digit by digit in O(n²) time.