LeetCode Q 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 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.
Given k will be between 1 and n! inclusive.

Example 1: Input: n = 3, k = 3 ; Output: "213"
Example 2: Input: n = 4, k = 9 ; Output: "2314"

Solution

Algorithm: Cantor Unfold
The detailed description can be found in wekipedia.
Cantor expansion is a double shot that is fully aligned to a natural number and is often used for spatial compression when building hash tables. The essence of Cantor’s expansion is to calculate the current order in all the order from small to large, and therefore reversible.

Code:

public String getPermutation(int n, int k) {
  // use list to store the num which we have chosen
  List<Integer> list = new ArrayList<>();
  for (int i = 1; i <= n; i++) 
    list.add(i);

  int[] fac = new int[n]; fac[0] = 1;
  for (int i = 1; i < n; i++) 
    fac[i] = fac[i - 1] * i;

  StringBuilder sb = new StringBuilder();
  k--;
  for (int i = n; i > 0; i--) {
    int index = k / fac[i - 1];
    k = k % fac[i - 1];
    sb.append(list.get(index));
    list.remove(index);
  }

  return sb.toString();
}

Reprint policy