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?
- 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 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
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();
}
}
}