字典序的一个生成算法

字典序的一个生成算法。
最近在LeetCode刷题,刷到一个题,链接:
https://leetcode-cn.com/problems/permutation-sequence/
这个题要求得长度为n的字典序列的第k个排列。
我们知道,字典序列是一个长度为n(n>=1),元素为1~n的无重复整数序列。
之前还真没仔细了解过如何按照顺序,从小到大生成这个序列。这次就探究一下。
我先在纸上枚举了n=3、4、5这几种简单的序列的生成,从中找到规律,然后推理出一般方法。
以n=4为例,字典序从小到大生成如下:

1234 → 1243 → 1324 → 1342 → 1423 → 1432 → 2134 → 2143 → 2314 → 2341 → 2413 → 2431 → 3124 → 3142 → 3214 → 3241 → 3412 → 3421 → 4123 → 4132 → 4213 → 4231 → 4312 → 4321

当我们拥有了从第m个排列到m+1个排列的生成方法时,就可以写一个算法findNext(),通过k-1次生成排列,就可以求出第k次的排列。

那么接下来就是寻找字典序的规律:
我们能够知道 如果当前字典序排列为M,假设M的下一个字典序为N,N也有下一个字典序O,那么有以下推论:

1. N = findNext(M)
2. O = findNext(N)
3. M < N < O

所以可得:N是大于M的最小的排列
既然我们要生成这样的一个排列,那么就要尽可能变动位数更低的数去增大序列:
以 findNext(1243)为例,为了尽可能变动位数更低的数去增大序列,由于“43”已经是降序排列的子序列,无法通过变动“4”这个位及更低的位去增大序列,那么只能从上一位“2”去增大序列,所以我们要从“43”这个降序序列中找到一个最的数“3”,换到“2”的位置,把“2”放入降序序列中,然后重新按照升序排序,这样就生成了“1324”,即1324 = findNext(1243)
所以我们有以下思路:

1. 从最低位开始寻找最长的递减序列L的最高位i
2. 如果i是最高位,证明已经是最大的字典序,算法结束;如果不是,取i的上一位j,从L中找到大于j的最小值k,然后交换jk位置
3. 对L进行升序排序,把L变为最小序列

Java代码如下:

public class GetPermutation {
    public static String getPermutation(int n, int k) {
        if(n <= 0 || k <= 0){
            return "";
        }
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = i + 1;
        }
        for (int i = 1; i < k; i++) {
            findNext(array);
        }
        return intArrayToString(array);
    }
    public static void findNext(int[] array){
        if(array != null && array.length > 1){
            int left_exchange_index = -1;
            //找到最长逆序的上一位
            for (int i = array.length - 1; i > 0; i--) {
                if(array[i - 1] < array[i]){
                    left_exchange_index = i - 1;
                    break;
                }
            }
            //如果还有更大的序列
            if(left_exchange_index != -1){
                //找到交换点的位置
                int right_exchange_index = findExchangeIndex(array, left_exchange_index);
                //交换
                exchange(array, left_exchange_index, right_exchange_index);
                //对交换后的序列升序排序
                sortRight(array, left_exchange_index + 1);
            }
        }
    }
    public static int findExchangeIndex(int[] array, int left_exchange_index){
        int left = left_exchange_index + 1;
        int right = array.length - 1;
        int temp = array[left_exchange_index];
        int middle = (left + right) / 2;
        while(left < right){
            //找到逆序内大于目标值的最小值
            if(array[middle] > temp && array[middle + 1] < temp){
                return middle;
            }else if(array[middle] < temp){
                right = middle - 1;
                middle = (left + right) / 2;
            }else {//array[middle + 1] > temp
                left = middle + 1;
                middle = (left + right) / 2;
            }
        }
        //就剩一个,只能和它换了
        if(left == right){
            return left;
        }
        return -1;
    }
    public static void exchange(int[] array, int left, int right){
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
    public static void sortRight(int[] array, int left){
        Arrays.sort(array, left, array.length);
    }
    public static String intArrayToString(int[] array){
        StringBuffer temp = new StringBuffer();
        for(int value : array){
            temp.append(value);
        }
        return temp.toString();
    }
    public static void main(String[] args) {
        System.out.println(getPermutation(4, 9));
    }
}

该算法能够计算出长度为n的字典序的第k个排列。

后来啊,我想了想,这个方法有些慢,毕竟k次移动,只有最后一次是有意义的,之前的k-1次移动都是白白浪费了运算。于是打算优化一下算法。
从优化生成字典序的方法开始吧,上面的算法,移动次数很多,这次优化可以采用回溯法处理。思路如下图所示:(本图来自Leetcode该题优秀题解,自己不想画图了,借用一哈)

生成字典序的优化思路如下:

1. 构造一个1~n的升序序列N
2. 从小到大逐个取N中的数,递归放入空序列M中
3. 当该序列的数全部用光时,记录该序列,拿走M中尾数字,回溯
4. 来到上一层,证明该层刚才递归用的数字已经用过了,从M尾部拿出,从N中取更大的一个数,递归放入M,回到步骤2
5. 当最外层使用了N中最大的数,并且回溯之后,证明所有序列已经生成,算法结束。

Java代码如下:

class Solution {
    public List> permute(int[] nums) {
        List> res = new ArrayList<>();
        List temp = new ArrayList<>();
        boolean[] used = new boolean[nums.length];

        arrange(res, used, nums, temp);

        return res; 
    }
    
    public static void arrange(List> res, boolean[] used, int[] nums, List temp){
        if(temp.size() == nums.length){
            res.add(new ArrayList<>(temp));
            return;
        }
        for(int i = 0; i < used.length; i++){
            if(used[i] == false){
                used[i] = true;
                temp.add(nums[i]);
                arrange(res, used, nums, temp);
                used[i] = false;
                temp.remove(temp.size() - 1);
            }
        }
        return;
    }
}

使用的used数组是为了记录该位置的数字是否使用过。

有了这个递归思路之后,通过剪枝的操作,就可以快速定位第k个字典序所在的分支,直接找到并返回。
以n = 4, k = 9为例 所求序列为 L

  1. 以1开头的序列一共有 3*2 = 6个
    因为k = 9 > 6
    所以L肯定不以1开头。
  2. 以2开头的序列也有 3*2 = 6 个
    以2为开头的序列应该是第7个至第12个
    因为 7 < k < 12
    所以L以2开头。
  3. 以21开头的序列一共有 2*1 = 2个
    以21开头的序列应该是第7个至第8个
    因为 8 < k
    所以L不以21开头
  4. 以23开头的序列一共有 2*1 = 2个
    以23开头的序列应该是第9个至第10个
    因为 k == 9
    所以L以23开头且是23开头的第一个数,就是2314

求解完毕。

将剪枝操作放在递归之前,即可求解,Java代码如下:

public class GetPermutation_better {
    public static String getPermutation(int n, int k) {
        int[] list = new int[]{1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
        int k_inner = k;
        Map used = new HashMap<>(16);
        for (int i = 1; i <= n; i++) {
            used.put(i, false);
        }
        List array = new ArrayList<>();

        arrange(array, used, k_inner, list);

        StringBuffer buffer = new StringBuffer();
        for(int temp : array){
            buffer.append(temp);
        }
        return buffer.toString();
    }

    public static void arrange(List array, Map used, int k, int[] list){
        if(array.size() == used.size()) {
            return;
        }
        int inner_k = k;
        for (int i = 1; i <= used.size(); i++) {
            if(used.get(i)){
                continue;
            }else {
                int num = used.size() - array.size() - 1;
                //判断当前的这个值,是否在这个分支内
                if(inner_k <= list[num]){
                    array.add(i);
                    used.put(i, true);
                    arrange(array, used, inner_k, list);
                }
                else {//不在就切换到下一个分支,去掉之前的个数
                    inner_k = inner_k - list[num];
                }
            }
        }
    }
    public static void main(String[] args) {
        System.out.println(getPermutation(3, 2));
    }
}

为了不再多构造一个int数组来存递增数列,将boolean数组升级为HashMap,兼具int数组与used数组的功能。
由于每层遍历从1开始,可能会遇到已经用过的数,这种情况下,不能剪枝,因为剪枝只针对还没有用过的数的分支,所以要先判断该数是否用过,再判断是否需要剪枝。
该算法不使用递归:

public class GetPermutation_best {
    public static String getPermutation(int n, int k) {
        int[] list = new int[]{1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
        int k_inner = k;
        Map used = new HashMap<>(16);
        for (int i = 1; i <= n; i++) {
            used.put(i, false);
        }
        List array = new ArrayList<>();

        arrange(array, used, k_inner, list);

        StringBuffer buffer = new StringBuffer();
        for(int temp : array){
            buffer.append(temp);
        }
        return buffer.toString();
    }

    public static void arrange(List array, Map used, int k, int[] list){
        int inner_k = k;
        for (int i = 1; i < used.size(); i++) {
            int num = used.size() - array.size() - 1;
            int integer = inner_k / list[num];
            int rest = inner_k % list[num];
            int index;
            if(rest == 0){
                index = integer;
                inner_k = list[num];
            }else {
                index = integer + 1;
                inner_k = rest;
            }
            array.add(getNum(index, used));
        }
        array.add(getNum(1, used));
    }
    public static int getNum(int index, Map used){
        int counter = 0;
        for (int i = 1; i <= used.size(); i++) {
            if(!used.get(i)){
                counter++;
            }
            if(index == counter){
                used.put(i, true);
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(getPermutation(3, 3));
    }
}

两种优化算法均为O(n^2)时间复杂度。

你可能感兴趣的