LeetCode - Permutation Sequence | Darren's Blog

Given n and k , return the k-th permutation sequence. Note: given n will be between 1 and 9 inclusive.

the permutations with the same first number are in a group. you will realize there is 
n groups, each of (n−1)! numbers. The permutations in each group are sorted as they are as a universal group. So our algorithm can work as follows: find which group the k-th permutation belongs to, extract the common first number from the list of numbers and append it to the construction of the permutation, and iteratively find within that group the (((k−1)%(n−1)!)+1)-th permutation.
From http://fisherlei.blogspot.com/2013/04/leetcode-permutation-sequence-solution.html
那么这里，我们把a1去掉，那么剩下的permutation为
a2, a3, .... .... an, 共计n-1个元素。 n-1个元素共有(n-1)!组排列，那么这里就可以知道

设变量K1 = K
a1 = K1 / (n-1)!

同理，a2的值可以推导为
a2 = K2 / (n-2)!
K2 = K1 % (n-1)!
 .......
a(n-1) = K(n-1) / 1!
K(n-1) = K(n-2) /2!

an = K(n-1)

public String getPermutation(int n, int k) {

        // Create a list of 1, 2, ..., n, and compute the number of permutations as "groupSize"

        List<Integer> list = new LinkedList<Integer>();

        int groupSize = 1;

        for (int i = n; i >= 1; i--) {

            list.add(0, i);

            groupSize *= i;

        }

        // Invalid k

        if (k > groupSize)

            return null;

        // Construct the k-th permutation with a list of n numbers

        // Idea: group all permutations according to their first number (so n groups, each of

        // (n-1)! numbers), find the group where the k-th permutation belongs, remove the common

        // first number from the list and append it to the resulting string, and iteratively

        // construct the (((k-1)%(n-1)!)+1)-th permutation with the remaining n-1 numbers

        StringBuilder builder = new StringBuilder();

        while (n > 0) {

            groupSize /= n;

            int groupIndex = (k-1) / groupSize;

            builder.append(list.remove(groupIndex));

            n--;

            k = ((k-1) % groupSize) + 1;

        }

 

        return builder.toString();

    }

Read full article from LeetCode - Permutation Sequence | Darren's Blog