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 k^th permutation sequence.

https://oj.leetcode.com/problems/permutation-sequence/

计算1~n数字的第k个排列

思路1：从小到大生成同时计数，直到第k个。 肯定超时试都不用试。。

思路2：直接根据规律计算第k个排列。

    分析：1~n个数共有n!个排列，1开头的有(n-1)!个，2开头的(n-1)!个，...n开头的有(n-1)!个。因此用k/(n-1)!就确定了第一位数字，然后依次类推（用过的数字要去除），继续在(n-1)!个数中找第k%(n-1)!个数。

思路2代码：

public class Solution {    public String getPermutation(int n, int k) {        int[] num = new int[n];        int permSum = 1;        for (int i = 0; i < n; i++) {            num[i] = i + 1;            permSum *= (i + 1);        }        StringBuilder sb = new StringBuilder();        k--;//change to base 0        for (int i = 0; i < n; i++) {            permSum = permSum / (n - i);            int selected = k / permSum;            sb.append(num[selected]);            for (int j = selected; j < n - i - 1; j++)                num[j] = num[j + 1];            k = k % permSum;        }        return sb.toString();    }    public static void main(String[] args) {        System.out.println(new Solution().getPermutation(4, 10));    }}

参考：

http://blog.csdn.net/havenoidea/article/details/12837441

http://www.cnblogs.com/TenosDoIt/p/3721918.html