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.

// mathematic analysis: n! = n * (n-1)! ==> the position of the first element of the kth sequencen is k / (n-1)!. // keep doing this: k = k % (n-1)!, remove the selected element, ...

public class Solution {
    public String getPermutation(int n, int k) {
        ArrayList list = new ArrayList();
        int count = 1;
        for(int i = 1; i <= n; i++){
            list.add(i);
            count *= i;
        }
        k--; // index starts from 0;
        StringBuilder ret = new StringBuilder();
        for(int i = 0; i < n; i++){   // index starts from 0;
            count = count / (n - i);  // get (n-1)!, (n-2)!, ...
            int pos = k / count;
            k = k % count;
            ret.append(list.get(pos));
            list.remove(pos);
        }
        return ret.toString();
    }
}