Permutation Sequence (Kth)

▶

Steps

setup

Initialize factorial array

Create a factorial array of size n with all elements initialized to 1. This array will store factorial values from 0! to (n-1)!.

💡 Precomputing factorials allows quick calculation of how many permutations start with each number at each position.

Line:

factorial = [1] * n

💡 Factorials represent the number of permutations possible for the remaining positions.

setup

Compute factorial values

Compute factorial values for indices 1 and 2 by multiplying the previous factorial by the current index.

💡 This step fills the factorial array with correct values to use for index calculations later.

Line:

for i in range(1, n):
    factorial[i] = factorial[i - 1] * i

💡 factorial[1] = 1, factorial[2] = 2, representing 1! and 2! respectively.

setup

Initialize numbers list

Create a list of numbers from 1 to n to represent the available digits for the permutation.

💡 This list will shrink as numbers are chosen for the permutation.

Line:

numbers = list(range(1, n + 1))

💡 The numbers list starts as [1, 2, 3], representing all digits to choose from.

setup

Adjust k to zero-based index

Subtract 1 from k to convert it from 1-based to zero-based indexing for easier calculations.

💡 Zero-based indexing aligns with array indices and factorial calculations.

Line:

k -= 1  # zero-based index

💡 k changes from 3 to 2, meaning we want the 2nd index permutation in zero-based terms.

traverse

Calculate index for first position

Calculate idx by dividing k by factorial[2] (2!). idx = 2 // 2 = 1. This selects the second number in the list for the first position.

💡 This determines which number to pick first based on how many permutations each number leads.

Line:

idx = k // factorial[i]

💡 Choosing index 1 means the first digit is '2' (numbers[1]).

traverse

Update k after first selection

Update k to k modulo factorial[2], k = 2 % 2 = 0. This resets k for the next position's calculation.

💡 Updating k narrows down the position within the smaller permutation block.

Line:

k %= factorial[i]

💡 k=0 means the next selection is the first in the remaining permutations.

insert

Append first chosen number and remove it

Append '2' (numbers[1]) to the result and remove it from the numbers list, leaving [1, 3].

💡 Removing the chosen number prevents reuse and shrinks the problem size.

Line:

result.append(str(numbers[idx]))
numbers.pop(idx)

💡 The first digit of the permutation is fixed as '2'.

traverse

Calculate index for second position

Calculate idx = k // factorial[1] = 0 // 1 = 0. Select the first number in the updated list [1,3].

💡 This picks the next digit based on the updated k and factorial values.

Line:

idx = k // factorial[i]

💡 Choosing index 0 means the second digit is '1'.

traverse

Update k after second selection

Update k = k % factorial[1] = 0 % 1 = 0, preparing for the last digit selection.

💡 k remains zero, indicating the first permutation in the last block.

Line:

k %= factorial[i]

💡 k=0 means the next digit is the first in the remaining list.

insert

Append second chosen number and remove it

Append '1' (numbers[0]) to the result and remove it from the list, leaving [3].

💡 The permutation is building with the second digit fixed.

Line:

result.append(str(numbers[idx]))
numbers.pop(idx)

💡 The permutation so far is '21'.

traverse

Calculate index for last position

Calculate idx = k // factorial[0] = 0 // 1 = 0. Select the only remaining number '3'.

💡 The last digit is chosen from the remaining single number.

Line:

idx = k // factorial[i]

💡 The last digit completes the permutation.

insert

Append last chosen number and remove it

Append '3' to the result and remove it from the numbers list, which becomes empty.

💡 The permutation is now complete with all digits chosen.

Line:

result.append(str(numbers[idx]))
numbers.pop(idx)

💡 The final permutation string is '213'.

reconstruct

Return final permutation string

Join the result list into a string and return it as the kth permutation.

💡 This step outputs the final answer after all selections.

Line:

return ''.join(result)

💡 The algorithm efficiently computed the 3rd permutation without enumerating all permutations.

def getPermutation(n, k):
    factorial = [1] * n  # STEP 1
    for i in range(1, n):  # STEP 2
        factorial[i] = factorial[i - 1] * i
    numbers = list(range(1, n + 1))  # STEP 3
    k -= 1  # zero-based index adjustment STEP 4
    result = []
    for i in range(n - 1, -1, -1):  # STEP 5-12
        idx = k // factorial[i]  # STEP 5,8,11
        k %= factorial[i]  # STEP 6,9,12
        result.append(str(numbers[idx]))  # STEP 7,10,12
        numbers.pop(idx)
    return ''.join(result)  # STEP 13

if __name__ == '__main__':
    print(getPermutation(3, 3))  # Output: '213'

📊

Permutation Sequence (Kth) - Watch the Algorithm Execute, Step by Step

Watching this step-by-step reveals how the factorial number system helps directly compute the kth permutation without generating all permutations.

setup

1

0

1

1

1

2

Result: ""

fill_row

1

0

1

1

i

2

2

Result: ""

setup

1

0

2

1

3

2

Result: ""

setup

1

0

2

1

k

3

2

Result: ""

compare

1

0

idx

2

1

i

3

2

Result: ""

move_left

k

1

0

idx

2

1

i

3

2

Result: ""

delete

k

1

0

3

1

Result: "2"

compare

idx

1

0

i

3

1

Result: "2"

move_left

idx

1

0

i

3

1

Result: "2"

delete

k

3

0

Result: "21"

compare

idx

3

0

Result: "21"

delete

Result: "213"

record

Result: "213"

Key Takeaways

✓ The factorial number system partitions permutations into blocks, allowing direct calculation of the kth permutation without generating all permutations.

This insight is hard to see from code alone because the math behind factorial indexing is abstract without visualization.

✓ At each step, the algorithm selects a digit by dividing k by the factorial of remaining positions, then updates k to the remainder, progressively narrowing down the permutation.

Seeing k and idx update step-by-step clarifies how the algorithm zooms into the correct permutation.

✓ Removing chosen numbers from the list ensures no repeats and reduces the problem size, which is visually clear when watching the array shrink.

This concrete example shows how the numbers list changes, which is less obvious when reading code.