---
title: Permutation Sequence
date: 2022-06-23
tags: ["permutation", "recursion"]
canonical: https://invariant.khalilli.ai/blog/permutation-sequence/
license: CC BY-SA 4.0
---
> **Problem:** The set [1, 2, 3, ..., n] contains a total of n! unique permutations. Given n and k, return the kth permutation sequence.
This problem is really cool and helpful to gain intuition on permutation problems.
Both recursive and iterative approaches are actually similar, but I will explain recursive approach, because it's much more native way for this problem.
**Core idea here is**: think the problem recursively as,
> **Theorem:** Proof: Initially for the first index of number, there are n! options. K initially resides in [1...K...N!] range. But for each number, there is block_size. What is this block size? Block size is it's (for each number) total number of contributions on current index to the permutations.
> Initially there are n numbers available as a choice. For next id there are n-1, for next after next there are n-2 etc.. You can think about that as a pigeon-hole principle.
>
> **0. For the 0th state:** n! is the initial block size [this state is abstact]
> **1. For the first index:** prev_block_size / n -> n!/n
> **2. For the second index:** prev_block_size / n-1 -> n!/n*(n-1)
> **3. For the third index:** prev_block_size/(n-2) -> n! / n * (n-1) \* (n-2)
> ...
**To find k, n, block_size for the next recursive state?**
> **Approach:** 1. new k will be k % curr_block_size (you can clearly see it from the pictures above). new k for the next recursive part will reside within borders of the previous block.
> 2. next n will be, n-1. will also delete n from the selection space.
> 3. new block_size will be, previous_block_size / new_space
```python
class Solution:
def getPermutation(self, n: int, k: int) -> str:
return self.solve(n, k)
def solve(self, n, k):
'''
123
132
213
231
312
321
how many permutations?
n * (n-1) * (n-2) [main range]
main range: 1...n!
main blocksize: n!//n (for example: 3 numbers, 3! permutations, 3!//3 block size)
main formula: block_size * numbers = permutationsize
second range: 1...(n-1)!
second blocksize:
second formula: block_size * (n-1) = (n-1)!
K ?
1.... K .... n!
(k // block_size + 1) -> number
k % block_size -> new_k (for remaining partition)
initial_block_size = n!
[2,3,1]
'''
import math
nums = [i for i in range(1, n+1)]
def recurse(n, k, block_size, res):
if n == 0:
return res
block_size = block_size // n
numidx = k // block_size
res += str(nums[numidx])
del nums[numidx]
return recurse(n-1, k % block_size, block_size, res)
return recurse(n, k-1, math.factorial(n), '')
```
**Further Research**
- Make research about the factorial number system
