字典序的一个生成算法

字典序的一个生成算法。
最近在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的最高位i2. 如果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个排列。