[Leetcode] 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):

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.

In order to handle this problem, we use some mathematical method and recursively compute the digit on each position.

We have a list of integer from 1...N where we could choice from. Since the permutation would use up all the integers in this list. When list has only 1 elements left, then this means we have pick out n-1. And what we need to do is just pick out this element, then we are done.

What if there are multiple numbers in the list? We need to determine which to choose by the number k.  If we have m elements in the list, then we now that there are m! permutation, and if we pick one, then there are (m-1)! permutation, meaning each leading elements would appear (m-1)! times. That is we choose list[k/(m-1)!] as this step choice, and we recursive on the m-1 with k = k%(m-1) (since we have determine the first element, there are already k/(m-1)!*(m-1)! elements less than us). However, pay great attention to k%(m-1) == 0, this means we actually get the last permutation in the bunch leading with k/(m-1)! - 1, this is a corner case and should be handle separately, since it is the last one, after picking the leading digit, we could just appending all the digits still in list now reversely.

Let's go over some simple examples.

Suppose n = 4 and k = 4.

1. step size (m-1)! = 6. In the first step, we choose 4 / 6 = 0th element in the list which is 1. And recursive with n = 3 and k = 4 % 6 = 4, the list now is 2 3 4;
2. step size (m-1)! = 2. In the second step, we choose 4 / 2 = 2nd element, however notice that 4 % 2 = 0. So we actually want the last permutation leading with the 1st element in list which is 3. That is 3 4 2, we append it to the result and return.
3. Finally, we get 1 3 4 2.

Here is another example.

Suppose n = 4 and k = 3.

1.  step size (m-1)! = 6. In the first step, we choose 4 / 6 = 0th element in the list which is 1. And recursive with n = 3 and k = 4 % 6 = 4, the list now is 2 3 4;
2. step size (m-1)! = 2. In the second step, we choose 3 / 2 = 1st element which is 3. And recursive with n = 2 and k = 3 % 2 = 1, the list now is 2 4;
3. step size (m-1)! = 1. In the third step, we choose 1 / 1 = 1st element. However 1 % 1 = 0, so we choose 0th element which is 2 and appending the remaining ones reversely. 
4. Finally we get 1 3 2 4.

public class Solution {
    List<Integer> list = new ArrayList<Integer>();
    public String getPermutation(int n, int k) {
        for(int i = 1; i <= n; i++) {
            list.add(i);
        }
        return dfs("", n, k);
    }
    
    private String dfs(String cur, int n, int k) {
        if(n == 1) {
            return cur + list.get(0); // base case, the last element
        }
        else {
            int num = 1;
            for(int i = 1; i < n; i++)
                num *= i; // step size for this step
            int index = k / num;
            int residual = k % num;
            if(residual != 0) {
                cur = cur + list.get(index);
                list.remove(index);
                return dfs(cur, n-1, residual);
            }
            else {
                cur = cur + list.get(index-1);
                list.remove(index-1);
                for(int i = list.size() - 1; i >= 0; i--) {
                    cur = cur + list.get(i);
                }
                return cur;
            }
        }
    }
}