Question

link

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]
两个解法。
第一，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;
}