Permutation Sequence

Permutation Sequence asks for the k-th permutation of the numbers 1…n in sorted order — without generating the ones before it. The trick is to treat k as a number written in the factorial number system, letting you read off each digit directly.

The slow way first

The obvious idea: generate every permutation in order and stop at the k-th. There are n! permutations, so even just walking up to k can mean producing up to n! strings. That is O(n! · n) — hopeless for n as small as 13.

The question to ask: can I figure out the first digit without listing anything? It turns out you can, because the permutations come in predictable blocks.

The idea: pick each digit with factorials

Sort the digits: [1, 2, ..., n]. Among all n! permutations, the first (n-1)! of them start with the smallest digit, the next (n-1)! start with the second, and so on. So the leading digit is decided entirely by which block k falls into.

Switch to a 0-indexed k (subtract 1). With block size fact = (n-1)!, the index of the leading digit is k // fact. Take that digit out of the pool, set k %= fact, shrink fact by dividing out the next count, and repeat for the next position.

The key insight: k // fact tells you which block, and k % fact is your position within that block — exactly the recursive structure of permutations.

Walk through it

Step through the animation. For n = 3, k = 3 we use k0 = 2. The block size starts at 2! = 2, so the leading digit is digits[2 // 2] = digits[1] = 2. Then k becomes 0, the pool shrinks to [1, 3], and the remaining picks fall out as 1 then 3, giving "213".

Pseudocode

digits = [1, 2, ..., n]
k = k - 1                      # make k 0-indexed
fact = (n - 1)!               # block size for the first position
result = ""
for remaining from n down to 1:
    index = k // fact          # which block / digit
    result += digits.pop(index)
    k %= fact                  # position within the block
    if remaining > 1:
        fact //= (remaining - 1)   # shrink block for next position
return result

The Python solution

def get_permutation(n, k):
    digits = list(range(1, n + 1))
    k -= 1
    fact = 1
    for i in range(1, n):
        fact *= i
    result = ""
    for remaining in range(n, 0, -1):
        index = k // fact
        result += str(digits.pop(index))
        k %= fact
        if remaining > 1:
            fact //= remaining - 1
    return result

• digits is the sorted pool we pick from; pop(index) both reads and removes a digit.
• k -= 1 converts to 0-indexed so the division math lines up.
• The first loop computes fact = (n-1)!, the block size for the leading digit.
• index = k // fact chooses the current digit; result += str(digits.pop(index)) commits it.
• k %= fact drops to the position within the chosen block.
• fact //= remaining - 1 shrinks the block size as the pool gets smaller (the next factorial down).

Complexity

We never enumerate permutations at all — we compute each digit directly. The O(n²) comes from n positions, each doing an O(n) pop from the list; the digits and result strings use O(n) space.

When this pattern shows up

Practice