Solution for Leet Code 60. Permutation Sequence

• By Arman Drismir • 3 minutes read

The set [1, 2, 3, …, n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in ascending order, we get the following sequence for n = 3:

  1. 123
  2. 132
  3. 213
  4. 231
  5. 312
  6. 321

The solution:

First, think about the problem of generating just the first number of the solution. To help visualize the pattern look at the first digit in the permutation set for n=4.

  1. 1 234
  2. 1 243
  3. 1 324
  4. 1 342
  5. 1 423
  6. 1 432

  7. 2 134
  8. 2 143
  9. 2 314
  10. 2 341
  11. 2 413
  12. 2 431

  13. 3 124
  14. 3 142
  15. 3 214
  16. 3 241
  17. 3 412
  18. 3 421

  19. 4 123
  20. 4 132
  21. 4 213
  22. 4 231
  23. 4 312
  24. 4 321

We can see that the first number starts at 1, and increments after 6 iterations. For an arbitrary n, how many iterations will it take before the first digit increments?

In general, the first digit increments after (n-1)! iterations.

So after every (n-1)! sized “block” the first digit will increase by 1. Therefore k // (n-1)! (where // is truncated division) will get us the number of “blocks” until the kth permutation. After each block the first digit increments by one, so k // (n-1)! will give us the first digit!


Now we try to find the next digit. If we draw out each block's remaining digits we can see that a similar-ish pattern emerges, where there are "blocks" that start with the same digit.
  1. _ 234
  2. _ 243

  3. _ 324
  4. _ 342

  5. _ 423
  6. _ 432


  7. _ 134
  8. _ 143

  9. _ 314
  10. _ 341

  11. _ 413
  12. _ 431


  13. _ 124
  14. _ 142

  15. _ 214
  16. _ 241

  17. _ 412
  18. _ 421


  19. _ 123
  20. _ 132

  21. _ 213
  22. _ 231

  23. _ 312
  24. _ 321

The pattern is a little hard to spot, but what is happening is that within each “super-block” of 6 permutations, we have a “sub-block” of size(n-2)!, and within each sub block we increment from 1 to 4, using the numbers that have not already been used by the first digit.

To get the second digit we calculate the size of our “sub-block”, in this case (4-2)! so 2. Then we calculate how many “sub-blocks” into our “super-block” k appears in. The formula for this is (k - super_block_start_index - 1) // sub_block_size.

So we can get how many “sub-blocks” into our “super-block” k appears at, but each “sub-block” has a different number, so how does this help us?

Key insight: Within each “super-block” the first character of the first “sub-block” is always the smallest available number. The first character of the second “sub-block” is always the 2nd smallest available number, etc…

So the second digit is (k - super_block_start_index - 1) // sub_block_size = x where x represents the xth smallest character we can still use.


This process is repeated, dividing the problem into smaller “sub-blocks” until we have resolved each character in the answer.

The final code for the problem is this:

from math import factorial

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        solution = ""
        
        nums = [x for x in range(1,n+1)]
        box_start_index = 0

        iteration = 0
        while len(solution) < n:
            box_size = factorial((n - iteration - 1))
            box_index = (k - box_start_index - 1) // box_size
            solution += str(nums[box_index])
            nums.pop(box_index)

            box_start_index += box_size * box_index
            iteration += 1


        return solution
Go to Top