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.
@tagbacktracking
@tagmath
Algorithm
Math
Assuming there are n
elements, the Kth 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 n1 elements. There are n1 elements in total (n1)!
group arrangement, then you can know
Set variable K1 = K
,
a1 = K1 / (n1)!
Similarly, the value of a2 can be derived as
a2 = K2 / (n2)!
K2 = K1 % (n1)!
.......
a(n1) = K(n1) / 1!
K(n1) = K(n2) / 2!
an = K(n1)
Cantor Expand
How to find the 16th (lexicographically) {1,2,3,4,5} permutation?
 First use 161 to get 15 — @note:@memorize: “1” is key to understand, kth permutation meaning k1,
@note@note
: eg: first permutation, k=1, after divided by4!, 3!, 2!, 1!
, should be0,0,0,0
, but1/1!
will gerate 1, which is wrong! so should be0/1! = 0

Divide 4 by 15! Get 0 remaining 15

Divide 3 with 15! Get 2 remaining 3

Divide 2 with 3! Get 1 remaining 1
 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