60. Permutation Sequence

Apparently, there are n! different permutations for given n. Suppose m is the first element, then there are n - 1! permuations for the rest n - 1 numbers. The case is similar to the second element to the nth element.

With that in mind, we can calculate the kth permutation from the first element to nth element. At first, we save 1 to n in a list num ascendently. Then we traverse from 1 to n, the index of the ith element in num equals to k / (n - i)! and k is updated to k % (n - i). The picked element is then removed from the list. Keep traversing until k = 0. Then we add the rest elements in num to the kth permutation.

This solution has two tricks:

1. Use a list to save candidate elements
2. Set k to k - 1 (synchronize index) can simplify the calculation

public String getPermutation(int n, int k) {
    StringBuilder sb = new StringBuilder("");
    List<Integer> num = new ArrayList<Integer>();
    for(int i = 1; i <= n; i++) // save candidate elements in a list
	num.add(i);
    int factorial = 1;
    for(int i = 1; i <= n - 1; i++)
	factorial *= i;
    k = k - 1; // an important trick
    for(int i = 1; i < n; i++) {
	if( k == 0 )
	    break;
	int index = k / factorial;
	k %= factorial;
	factorial /= (n - i);
	sb.append(num.get(index));
	num.remove(index);
    }
    for(int i = 0; i < num.size(); i++)
	sb.append(num.get(i));
    return sb.toString();
}