The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
General idea:
Grouping of each permutations.
For each n permutation, it belongs to one of n group. For example, for 3 permutation, each permutation belongs to either 1 group, 2 group or 3 group, as determined.
Another way to look at this is, all n=3 permutation consists of
1 + (permutations of 2, 3, 4) (total of 6)
2 + (permutations of 1, 3, 4)(total of 6)
3 + (permutations of 1, 2, 4)(total of 6)
4 + (permutations of 1, 2, 3)(total of 6)
K will determine what group the permutation is in. For example, if k = 1 or 2, then it belongs to group 1. This formation leads to recursive solution but there are iterative way.
Iterative
Given n, k and a list of unused number in order EG n = 4, k = 13, l = [1,2,3,4]
Find the most significant digit
Group and its size
To find the most significant digit is equivalent to finding what group the permutation is in.
We know the group size is (n – 1)! since if we fixed one number, the most significant digit, then we have (n – 1) space left to form numbers in our group and there are (n – 1)! of them For k = 13, we can see it is in the second group because each (k // group-size) = 2.
formula
group = k // (n – 1)!. The result is zero-indexed.
Most significant dig = group + 1
So for n = 4, k = 13, group = 13 // (2) = 2. Most significant dig = 3
Next iteration
Recursive
The problem repeats with less numbers: Since we know 2 is the most significant digit of the permutation we want, we are left with 3 numbers [1,3,4]. The permutations are 1 + perm(2,4) 2 + perm(1,4) 4 + perm(1,2)
Change n and k
Now, we let n = n – 1. For K, we only need to focus on the size 3 permutation within the chosen permutation from the beginning. In our example that would be group 3 of 3 + perm(1,2,4).
So the new k needs to remove all permutations before the chosen group. In our case, we need to remove all 1 + perm(2,3,4), which has size 6. new-k = k – (chosen-group-index) *(n – 1)!
For our case, new-k = 13 – 2 * 6 = 1.
So the group n = 3, k = 1 will be in is 1 //(2!) = 0 So the next permutation 1 + perm(2,4)
Finishing up the example
31 + 2 + perm(4) 31 + 4 + perm(1)
n = 2, k = 1 – (0 * 1) = 1
group = k // (n – 1)! = 1 //(1) = 1 So we choose 312 + perm(4) to proceed
n = 1, new_k = 1 – 1 * 0! = 1 – 1 = 0. group = k // (n – 1)! = 0 // 1 = 0. So we choose the first one.
Done
After we find the most significant dig, we want to find the second most significant digit. Also by knowing we are in the second group, we have eliminated the possibility in the first group.
def getPermutation(self, n: 'int', k: 'int') -> 'str':
res = ''
nums = [i for i in range(1, n + 1)]
facts = []
product = 1
for i in range(1, n + 1):
product *= i
facts.append(product)
k -= 1 # k is an index, so we need to subtract 1 to zero-index it
prev_index = 1
while n > 1:
group_size = facts[n - 2]
nth_dig_pos = k //group_size
nth_num = nums[nth_dig_pos]
res = res + str(nth_num)
nums.pop(nth_dig_pos)
new_k = k - nth_dig_pos * group_size
k = new_k
n -= 1
res = res + str(nums[0])
return res