Permutation Sequence
Permutation Sequence: return the k-th permutation (1-indexed, lexicographic) of 1..n — without generating them all.
- 1 <= n <= 9
- 1 <= k <= n!
Intuition
The permutation sequence problem asks for the k-th permutation of 1..n in lexicographic order. Generating all of them and indexing works only for tiny n — 9! is already 362,880 — so the answer has to be constructed directly.
The structure to exploit is that lexicographic order groups permutations into blocks. With n = 4, every permutation beginning with 1 comes before every one beginning with 2, and there are exactly 3! = 6 of each. So the first digit is determined by which block k falls into: divide by (n−1)! and the quotient picks the leading digit from the sorted list of unused digits.
The remainder then poses the same question one digit smaller — find the (remainder)-th permutation of what is left — so the process repeats with (n−2)!, and so on down to a single digit:
- Each step fixes one digit by division and reduces the problem by one, never enumerating anything.
The one implementation detail that removes all the awkwardness is switching to zero-based indexing immediately. Subtract 1 from k at the start, and every step becomes a plain divmod; with 1-based k you end up with off-by-one corrections at every level. This is the factorial number system, where each digit position carries a factorial weight instead of a power of ten.
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
Before reading on: price up what the direct approach costs here, then ask what you may assume the recursive call already handles correctly. Aim for O(n²) time and O(n) space.
Convert k to zero-based once
Set k = k - 1 before anything else. Every subsequent step is then a clean divmod, with no +1 or −1 corrections. Doing this conversion at each level instead is the most common source of off-by-one bugs in this problem.
Precompute the factorials
Compute 0! through (n−1)! up front. Each level needs the block size for the remaining digits, and n is at most 9, so this is a handful of multiplications done once rather than repeatedly inside the loop.
Keep the unused digits in sorted order
Hold [1, 2, …, n] in a list. Sorted order is what makes the quotient meaningful: index q in this list is the q-th smallest available digit, which is exactly what lexicographic order requires.
Divide to pick the digit, take the remainder for the rest
At each position with f = (remaining − 1)!, compute q, k = divmod(k, f). Remove the digit at index q from the list and append it to the answer. The remainder k is the position within that block, and it becomes the input to the next level.
Remove the digit after using it
Deleting the chosen digit from the list is what keeps later indices correct — the list must always contain only unused digits. Forgetting this produces repeated digits and a result that is not a permutation at all.
Cost of the construction
There are n positions and each removes an element from a list of size at most n, giving O(n²) time with a simple list — trivial for n ≤ 9. Space is O(n). Compare this with generating all permutations, which is O(n! × n) and infeasible past n = 10.
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.