# 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 = 1;
ArrayList<Integer> nums = new ArrayList<Integer>();
for (int i = 1; i < n; i++) {
fact[i] = fact[i-1] * i;
}
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;
}
}
``````