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.

For example n=4, k=17

• 1 2 3 4
• 1 2 4 3
• 1 3 2 4
• 1 3 4 2
• 1 4 2 3
• 1 4 3 2
• 2 1 3 4
• 2 1 4 3
• 2 3 1 4
• 2 3 4 1
• 2 4 1 3
• 2 4 3 1
• 3 1 2 4
• 3 1 4 2
• 3 2 1 4
• 3 2 4 1
• 3 4 1 2 <--- k = 17
• 3 4 2 1
• 3 1 2 3
• 4 1 3 2
• 4 2 1 3
• 4 2 3 1
• 4 3 1 2
• 4 3 2 1

In the first index position, each digits appears 6 times

When the first digit is set, in the second index position, each digits appears 2 times,

When the second digit is set, in the third index position, each digits appears 1 time.

Left digit is in the fourth position.

so the formula is as below:

a1 = k / (n - 1)!

k1 = k

a2 = k1 / (n - 2)!

k2 = k1 % (n - 2)!

... ...

an-1 = kn-2 / 1!

kn-1 = kn-2 / 1!

an = kn-1 / 0!

kn = kn-1 % 0!

Note: in the calculation k starts with 0, so we need to do k = k-1.

public String getPermutation(int n, int k) {
        if (n<1) {
            return "";
        }

        StringBuilder nums = new StringBuilder();
        int permutation = 1;

        for (int i=1; i<=n; i++) {
            //set number from 1..9
            nums.append(i);   
            //calculate n factorial
            permutation*=i;
        }

        //this is important, k starts with 1, but index starts with 0
        k = k-1;
        StringBuilder result = new StringBuilder();
        for (int i=0; i<n; i++) {
            permutation = permutation/(n-i);
            // Follow the logic: a0 = k/(n-1)! then 
            int digit = k/permutation;
            result.append(nums.charAt(digit));
            nums.deleteCharAt(digit);       
            k = k % permutation;            
        }

        return result.toString();
    }