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.

Table of Contents

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

LC 60 Permutation Sequence