[LeetCode] Permutation Sequence (Java)

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 (ie, for n = 3):

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

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Analysis

We can generate all permutations until we get the kth one. But it costs $O(n!)$ time.

Another way is to calculate every digit. For example, assuming we are going to solve the problem when n = 3 and k = 5. In fact, because k starts from 1, we need to subtract 1 from it to make it starting from 0. So we are going to find the permutation 4 now. To calculate the first digit, we can calculate it by k % (n – 1)! = 4 / 2! = 2, which is the position of 3 in array [1,2,3]. Now we need to delete 3 from the array, so the array becomes [1, 2]. And k should become 4 % 2! = 0. Now we calculate k / (n – 2)! = 0 / 1 = 0, which is the position of 1 in array [1, 2]. So the second digit should be 1. We need to delete 1 from the array. And there is only one entry left in the array. So the final digit should be 2. Finally we get the permutation: 312.

Code

I use an ArrayList to save the numbers, which can easily be used to fetch the number and delete it from the list.

Complexity

The complexity of this algorithm is $O(n)$.

  • shan

    good!! Would you please explain the reason using k–? why not use k? Thanks very much

    • decoet

      Our sequence starts from 0. But in the question, it starts from 1. For example, if we want to find the first permutation, in other words, k is 1, what we are going to find is the 0th permutation.

      • shan

        Thanks very much!

  • vishlesh

    How can we figure our or analyze that the first digit can be calculated by k/(n-1)!? can you please explain why it’s happening? thanks!