/*

    n个数有n!个排列，第k个排列，是以第（k-1）/(n-1)!个数开头的集合中第（k-1）%(n-1)!个数

     */

    public String getPermutation(int n, int k) {

        k--;

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

        StringBuilder res = new StringBuilder();

        int count =1;

        //以每个数字开头的集合有多少中排列

        for (int i = 2; i <= n -1; i++) {

            count*=i;

        }

        //记录哪些数字还没用

        for (int i = 1; i <=n ; i++) {

            list.add(i);

        }

        //回合数,也就是小集合的size

        int round = n-1;

        while (round>=0)

        {

            int num = list.get(k/count);

            res.append(num);

            list.remove(k/count);

            if (round>0)

            {

                k = k%count;

                count/=round;

            }

            round--;

        }

        return res.toString();

    }