60 Permutation Sequence – Medium¶

Problem:¶

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.

Thoughts:¶

In order to make calculation easier, we need to decrease k at the very beginning.

If n = 4, k = 9.

Decrease k to be 8. All index is starting at 0.

For the first number, is the (8 / 3!)th , which is 2 of the remaining number {1, 2, 3, 4}.

For the second number, is k1= (8%3!) , and order is k1 / 2!= 1 , which is 3 of the remaining number (1, 3, 4}

For the third number is k2 = k1 % 2! = 0, and order is k2 / 1! = 0, which is 1 of the remaining number of {1,4}

For the fouth number is k3 = k2 %1! = 0, and order is k3/ 0! = 0, which is 1 of the remaining number {4}

In order to make calculation correct, we assume 0! = 1

Solutions:¶

public class Solution {
    public String getPermutation(int n, int k) {
        int[] fact = new int[n];
        fact[0] = 1;
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(1);
        for (int i = 1; i < n; i++) {
            fact[i] = fact[i-1] * i;
            nums.add(i+1);
        }
        String result = "";
        k = k - 1;
        for (int i = 0; i < n; i++) {
            int index = k / fact[n-1-i];
            result = result + (nums.get(index) + "");
            nums.remove(index);
            k = k % fact[n-1-i];
        }
        return result;
    }
}