Question

Formatted question description: https://leetcode.ca/all/60.html

60. Permutation Sequence

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):

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.

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

@tag-backtracking
@tag-math

Algorithm

Math

Assuming there are n elements, the K-th permutation result string is a1, a2, a3, ..... ..., an So which number is a1?

So here, we remove a1, then the remaining permutation is a2, a3, .... .... an, a total of n-1 elements. There are n-1 elements in total (n-1)! group arrangement, then you can know

Set variable K1 = K, a1 = K1 / (n-1)!

Similarly, the value of a2 can be derived as

a2 = K2 / (n-2)!
K2 = K1 % (n-1)!
.......
a(n-1) = K(n-1) / 1!
K(n-1) = K(n-2) / 2!

an = K(n-1)

Cantor Expand

How to find the 16th (lexicographically) {1,2,3,4,5} permutation?

1. First use 16-1 to get 15 — @note:@memorize: “-1” is key to understand, k-th permutation meaning k-1, @note@note: eg: first permutation, k=1, after divided by 4!, 3!, 2!, 1!, should be 0,0,0,0, but 1/1! will gerate 1, which is wrong! so should be 0/1! = 0

2. Divide 4 by 15! Get 0 remaining 15

3. Divide 3 with 15! Get 2 remaining 3

4. Divide 2 with 3! Get 1 remaining 1

5. Divide 1 by 1! Get 1 more than 0

There are 0 numbers smaller than it is 1, so the first digit is 1.

There are 2 numbers that are smaller than it is 3, but 1 has appeared before, so it is 4.

There is 1 number smaller than it is 2, but 1 has appeared before, so it is 3.

There is 1 number smaller than it is 2, but 1, 3, and 4 have all appeared, so it is 5.

The last number can only be 2

So the arrangement is 1 4 3 5 2

Code

Java

import java.util.ArrayList;
import java.util.List;

public class Permutation_Sequence {

	public static void main(String[] args) {
        Permutation_Sequence out = new Permutation_Sequence();
        Solution s = out.new Solution();

        System.out.println(s.getPermutation(4, 17)); // 3412
    }

    // time: O(N)
    // space: O(N)
    public class Solution {
        public String getPermutation(int n, int k) {

            List<Integer> nums = new ArrayList<Integer>();
            List<Integer> factorial = new ArrayList<Integer>(); // total `n` elements
            factorial.add(1);
            for (int i = 1; i <= n; i++) {
                nums.add(i);

                // size=n+1, will be [1,1,2,6,24]
                // so that, factorial(k) is `k!`
                factorial.add(factorial.get(i - 1) * i);
            }


            StringBuilder result = new StringBuilder();
            k = k - 1; // k 变为 k - 1
            for (int i = n; i > 0; i--) {

                int digit = k / factorial.get(i - 1);
                result.append(nums.get(digit));

                k %= factorial.get(i - 1);
                nums.remove(digit); // remove by object
            }
            return result.toString();
        }
    }

}

All Problems

All Solutions