package pers.vic.basics.leetcode;


import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @description: 60. 排列序列  {@literal https://leetcode-cn.com/problems/permutation-sequence/}
 * @author Vic.xu
 * @date: 2020/12/22 0022 8:32
 */
public class J0060_H_GetPermutation {

    /*
    给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
    按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
    "123"
    "132"
    "213"
    "231"
    "312"
    "321"
    给定 n 和 k，返回第 k 个排列。

        1 <= n <= 9
        1 <= k <= n!
     */

    /**
     * 1. 如果用回溯找到所有结果集 ，然后再返回第K个效率肯定很低，不过鉴于题目中n小于等于9 可以试一试，果然，就算排列到k就终止，依然是只打败15%；
     * 2. 通过找规律的方式，假设n = 4； k=9;   2314
     * * 若以1 开头，则有 3!（6）种排列方式
     * * 若以2 开头，则有3!中排列方式，另外加上以1开头的6种共12种
     * *  12 > 9 故 ，第1位数字肯定是2； 12 - 9 = 3
     * * 剩下数字 1 3 4
     * **同理 以1开头的排列有 2！ = 2
     * ** 以3 开头的排列有 2！ 同时加上以1 开头的排列 共4种
     * ** 4 > 3,所以第2个数字肯定是3： 4-3 = 1
     * ***剩下数字 1 4
     * *** 以1 开头的数字有 1！ 一种  1>= 1  所以 第三个数字是1
     * **** 最后剩下的数字是4
     * 因此最终的结果是2314
     * ========整理下上面的思路：从高位往低位逐一寻找===================================
     * 假设 n = 5;k = 20
     * nums = [1, 2, 3, 4, 5]    数字个数对应的阶乘关系： [1, 2, 6, 24, 120]
     * 1. 第一位(n=5)：(20-1)/4! = 0 ，第一位是nums[0] = 1, 此时nums中去掉1 [2,3,4,5]；  k = k - 0 * 4! = 10;
     * 2. 第二位(n=4)：(10-1)/3! = 1 ，第二位是num[1] = 3,此时nums中去掉3   [2,4,5]      k = k - 1*3! = 4
     * 3. 第三位(n=3)：(4-1)/2! = 1,   第三位是nums[1] = 4,此时nums中去掉4  [2,5]        k = k-1*2! = 2
     * 4. 第四位(n=2): (2-1)/1! = 1,   第四位是nums[1] = 5 ,此时nums中去掉4  [2]         k = k-1*1! = 1
     * 5  第五位(n=1): (1-1)/0! = 0,   第五位是nums[0] = 2 ,此时nums中去掉2  []
     */
    public static String getPermutation(int n, int k) {
        StringBuilder res = new StringBuilder();
        //当前剩下的全部的可排列的数字[1,2....n] 从小到大排列
        List<Integer> nums = new ArrayList<>();
        //数字个数 和排列个数的关系
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i] = i * dp[i - 1];
            nums.add(i);
        }
        //开始从最高位逐一填充数字
        //当前位填充的数字 等于它前一个数字的阶乘  乘以  x,
        while (n > 0) {
            //前一位数的总排列书
            int preCount = dp[--n];
            int index = (k - 1) / preCount;
            res.append(nums.get(index));
            nums.remove(index);
            k -= index * preCount;
        }

        return res.toString();
    }


    /**
     * 通过回溯全排列的方式测试一下性能
     */
    public static String getPermutation2(int n, int k) {
        char[] cs = new char[n];
        for (int i = 0; i < n; i++) {
            cs[i] = (char) ('0' + i + 1);
        }
        List<String> list = new ArrayList<>();
        StringBuilder temp = new StringBuilder();
        dfs(list, temp, n, new boolean[n], k, cs);
        return list.get(k - 1);
    }

    public static void dfs(List<String> list, StringBuilder temp, int n, boolean[] used, int k, char[] cs) {
        if (list.size() >= k) {
            return;
        }
        if (temp.length() == n) {
            list.add(temp.toString());
            return;
        }

        for (int i = 0; i < n; i++) {
            if (used[i]) {
                continue;
            }
            temp.append(cs[i]);
            used[i] = true;
            dfs(list, temp, n, used, k, cs);
            used[i] = false;
            temp.setLength(temp.length() - 1);

        }
    }

    public static void main(String[] args) {
        //213
        System.out.println(getPermutation(3, 3));
        //2314
        System.out.println(getPermutation(4, 9));
        //13452
        System.out.println(getPermutation(5, 10));
    }
}