Question
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.
Stats
| Frequency | 1 |
| Difficulty | 5 |
| Adjusted Difficulty | 4 |
| Time to use | ---------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
This is a math problem. Trying to solve it using DFS like in “Permutation” or “N queen” will get time limit exceed exception.
This blog have a very good explanation of the math solution.
[Thoughts]
两个解法。
第一，DFS
递归遍历所有可能，然后累加计算，直至到K为止。
第二，数学解法。
假设有n个元素，第K个permutation是
a1, a2, a3, ..... ..., an
那么a1是哪一个数字呢？
那么这里，我们把a1去掉，那么剩下的permutation为
a2, a3, .... .... an, 共计n-1个元素。 n-1个元素共有(n-1)!组排列，那么这里就可以知道
设变量K1 = K
a1 = K1 / (n-1)!
同理，a2的值可以推导为
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)
Solution
I have written a math recursive solution and code is below. It’s very straight-forward.
There is also direct math solution. However, how to handle the removal of elements from the unmatched list is a tough problem. I saw a lot of people using swap to do it, but I don’t like this idea because of the bad readability of code.
Finally I found a readable code from this blog. It’s a very good solution.
My code
updated on my birthday this year
public String getPermutation(int n, int k) {
int index = k - 1;
List<Integer> nums = new ArrayList<Integer>();
for (int i = 1; i <= n; i++) {
nums.add(i);
}
String ans = "";
for (int i = n - 1; i >= 1; i--) {
int fact = factorial(i);
int nextIndex = index / fact;
index = index % fact;
ans += nums.remove(nextIndex);
}
ans += nums.get(0);
return ans;
}
private int factorial(int x) {
if (x == 0) return 0;
int ans = 1;
for (int i = 2; i <= x; i++) {
ans *= i;
}
return ans;
}