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.

Couldn't believe I spent two hours on this problem. I wouldn't say it's a very hard problem, just tricky.
Naturally I would think of using backtracking, well, apparently it will not pass the time limit. So I googled, and here goes this smart way.

We know that when one number is fixed, there are (n - 1)! ways to permute the rest numbers. This means in every (n - 1)! times, the number at certain position will change. For example, if n = 3 and k = 3, the first number should be the upper bound of 3 / 2!, which is 2. Or think in another way, there are only 2! permutations start with 1, so 1 cannot be the start number. 2 * 2! = 4, which means permutations start with 2 will occupy 3 and 4th position.

So,  num1 = k / factorial;

if the first position is fixed, we need to find the next k. And that is:

k2 = k % factorial.

I couldn't understand that at first, and then I figure out, it's the k2 - th number after num1 is fixed. Using our n = 3, k = 3 example, it is the 1st number start with 2.

Do it iteratively and problem is solved!

Update: 2015 - 01 - 08
The reason we need to use 0 ... n index is that we are using a boolean array to check if the number has been used. So use 0 ... n index will make the whole method more concrete.

And about the inner loop to determine which number is the next to add. Let's look at the example of n = 4 and k = 3.

(n - 1)! = 6, index = 0. The zeroth index in the whole array. No doubt num1 = 1.
k % (n - 1)! = 3, the third permutation in all permutations starts with 1. Index = k / (n - 2)! = 1, that is the index in the rest of the array.

So how to get that index? It is clear in the figure if 0 the leftover are 1, 2, 3. What if they are 0, 2, 3? So we need to count the unused numbers, and that's the reason we decrement index in the inner loop. 

public class Permutation {
    public String getPermutation(int n, int k) {
        int factor = 1;
        for (int i = 1; i < n; i++)
            factor *= i;
        //change k from 1...n index to 0...n 
        k--;
        boolean[] used = new boolean[n];
        String rst = "";
        for (int i = 0; i < n; i++)
        {
            int index = k / factor;
            k = k % factor;
            for (int j = 0; j < n; j++)
            {
                //we need to find the number that has not been used
                //n = 3, k = 4, after we find 2, the next index = 1
                //we need to find the (index + 1)'s number in {1,3}, which is 3
                if (!used[j])
                {
                    if (index == 0)
                    {
                        used[j] = true;
                        rst += String.valueOf(j + 1);
                        break;
                    }
                    else
                        index--;
                }
            }
            if (i < n - 1)
                factor /= (n - i - 1);
        }
        return rst;
    }
}