[LeetCode 60] Permutation Sequence

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

1. `"123"`
2. `"132"`
3. `"213"`
4. `"231"`
5. `"312"`
6. `"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]

a1, a2, a3, .....   ..., an

a2, a3, .... .... an, 共计n-1个元素。 n-1个元素共有(n-1)!组排列，那么这里就可以知道

a1 = K1 / (n-1)!

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++) {
}
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;
}
``````