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.

思路：这一题还是比較难，暴力全然是找死的，超时没二话。可是数学归纳的方法不是每一个人都能想到，看了非常多资料，也才刚理解了一些思想。

规律：已知n的值，学过排列组合知道共同拥有n！种排列。

第一位每一个数字开头的序列都有（n-1）！

个序列，因此n个数字所以共同拥有n！个序列。

以此类推。第二位每个数开头都有（n-2）！

个序列。

详细代码例如以下：

public class Solution {

    String str = "";

    public String getPermutation(int n, int k) {

    	int[] num = new int[n];

        int[] data = new int[n];//存阶乘的数据

        int i = 0;

        for(; i < n ;i++){

        	num[i] = i+1;

        	if(i == 0)

        		data[i] = 1;

        	else{

        		data[i] = data[i-1]*i;

        	}

        }

        k--;

        while(--i > -1){//循环得到各位数字

        	int k1 = k/data[i];

        	int p = k1+(n-1-i);//数字的位置

        	swap(n-1-i,p,num);

        	if((k = k %data[i]) == 0)//k==0结束

        		break;

        }

        for(int x:num)//得到str

        	str += x;

        return str;

    }

    //将数据插入，后面的依次后移

    public void swap(int i,int j,int[] num)

    {

    	int m = num[j];

        for(int k=j;k>i;k--)

        	num[k]=num[k-1];

        num[i]=m;

    }

}