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

Java