Permutation Sequence
Return the k-th permutation (1-indexed, lexicographic) of 1..n — without generating them all.
Intuition
Permutations starting with a fixed first digit form blocks of (n−1)! each. k ÷ (n−1)! says which digit leads; the remainder repeats the question one digit down. It's positional notation in the factorial number system.
Don't generate what you can count. There are (n−1)! permutations starting with each digit, so dividing k by that factorial tells you the leading digit outright, and the remainder is the same question one size smaller. Whenever a problem asks for the k-th item of an ordered family, look for arithmetic that jumps straight to it — enumerating 9! sequences to take one is the trap.
Approach
Blocks of (n−1)!
With n=4, permutations come in 4 blocks of 3! = 6: those starting 1, then 2, … idx = (k−1) // 6 picks the leader from the unused digits.
Recurse on the remainder
k = (k−1) % (n−1)! + 1 and repeat with the remaining digits and (n−2)!, and so on down to one digit.
Zero-index to keep it clean
Working with k−1 throughout turns every step into plain divmod.
Solution & live demo
Common pitfalls
Generating all permutations and indexing
return sorted(permutations(digits))[k - 1]
for i in range(n, 0, -1):
f = factorial(i - 1)
idx, k = divmod(k, f)
out.append(digits.pop(idx))That's O(n!) work and memory to keep one result — n = 9 means 362,880 sequences built and discarded. The factorial arithmetic gets there in n steps.
Forgetting to convert k to 0-based
idx, k = divmod(k, f)
k -= 1 ... idx, k = divmod(k, f)
k arrives 1-indexed but divmod and list indexing are 0-based, so every block boundary lands one place late — with k an exact multiple of f you select the next digit entirely. One decrement up front fixes all n steps.
Leaving the used digit in the pool
out.append(digits[idx])
out.append(digits.pop(idx))
Each digit is used once, and removing it keeps the remaining list sorted so the next idx still means "the idx-th smallest unused digit". Leaving it in makes every later index refer to the wrong digit.
Edge cases
Every divmod yields index 0 → smallest permutation 123…n.
Always picks the last remaining digit → fully descending permutation.