第k个排列

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

 

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

 

"123"

"132"

"213"

"231"

"312"

"321"

给定 n 和 k，返回第 k 个排列。

 

说明：

 

给定 n 的范围是 [1, 9]。

给定 k 的范围是[1,  n!]。

示例 1:

 

输入: n = 3, k = 3

输出: "213"

示例 2:

 

输入: n = 4, k = 9

输出: "2314"

 

回溯法

以下是全排列的代码，但是显示超时

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

public static String getPermutation(int n, int k) {
    if(n == 0){
        return "";
    }
    int[] nums = new int[n];
    for(int i =0;i<n;i++){
        nums[i] = i+1;
    }
    List<Integer> list1 = new ArrayList<>();
    dpf(nums,list1);
    String str2="";
    String str = String.valueOf(list.get(k-1));
    if (str != null && !"".equals(str)) {
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) >= 48 && str.charAt(i) <= 57) {
                str2 += str.charAt(i);
            }
        }
    }
    return str2;
}

private static void dpf(int[] nums, List<Integer> list1) {
    if(list1.size() == nums.length){
        list.add(new ArrayList<>(list1));
    }else {
        for(int i =0;i<nums.length;i++){
            if(list1.contains(nums[i])){
                continue;
            }
            list1.add(nums[i]);
            dpf(nums,list1);
            list1.remove(list1.size()-1);
        }
    }
}

主函数

public static void main(String[] args) {
    System.out.println("请输入n与k的值");
    Scanner sc = new Scanner(System.in);
    String str = sc.nextLine().trim();
    String[] temp = str.split(",");
    int n =0;
    for(int i=0;i<temp[0].length();i++){
        if (temp[0].charAt(i) >= 48 && temp[0].charAt(i) <= 57) {
            n = temp[0].charAt(i)-'0';
        }
    }
    String str2 ="";
    for(int i=0;i<temp[1].length();i++){
        if (temp[1].charAt(i) >= 48 && temp[1].charAt(i) <= 57) {
            str2 += temp[1].charAt(i);
        }
    }
    System.out.println(getPermutation(n, Integer.parseInt(str2)));
}

 

进行优化的回溯法+剪枝策略

以上的

思路1

即使用回溯的思想，依次得到全排列，输出所求的第 k个全排列即可。但事实上，我们不必求出所有的全排列。基于以下几点考虑：

解题思路

k要先变成k-1，因为现在用的是下标值，是以0开头的，k–;

用k对(n-1)!取商，结果为数据 余数为下一个数字

比如n=4,这样排列出来的数据就有[1234,1243,1324,1342,1423,1432,2134,
2143,2314,2341,2413,2431,3124...]

第一轮：
可以看到以1开头的有3*2*1 = 6种，同理2.3.4的都是这样
这样8/6 = 1..2（商为1，余数为2）， 结果数据就是索引为1的2（第0个是1）
然后把2从数组中移除

第二轮
这时候数据把2除外就有[134,143,314,341,413,431]
可以看到以1开头的有2*1 = 2种，同理3.4的都是这样
上一把余数是2，所以2/2 = 1..0，结果数据就是索引为1的3（第0个是1）

第三轮
这时候数据把2除外就有[14,41]
可以看到以1开头的有1 =1种，同理4的都是这样
上一把余数是0，所以0/1 = 0..1，结果数据就是索引为0的1（第0个是1）
 

思路2

/*
     * @Author liuhaidong
     * @Description方法一  回溯法加剪枝
     * @Date 9:59 2019/9/30 0030
     **/
    public static String getPermutation(int n, int k) {
        int fact = 1;
        //保存总的n!
        List<Integer> nums = new ArrayList<>();
//        int[] nums = new int[n];
        for(int i =0;i<n;i++){
            nums.add(i,i+1);
            fact *= i+1;
        }
        //这个时候算出总的阶乘到时候需要几的阶乘时候那就除以n-i
        k -= 1;
        //因为k是从0开始的，所以要减去1
        StringBuilder sb = new StringBuilder();
        for(int i =0;i<n;i++){
            fact = (int)Math.floor(fact/(n-i));
            //这个时候算出(n- 1)!
            int index = (int)Math.floor(k/fact);
            //这个时候算出第一个index的位置
            sb.append(nums.get(index));
            //把找到的放进去
            k %=fact;
            nums.remove(index);
            //然后去掉已经找到的然后重新遍历其他的
        }
        return String.valueOf(sb);
    }