# 字典序的一个生成算法

https://leetcode-cn.com/problems/permutation-sequence/

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

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

``````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));
}
}``````

``````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){
return;
}
for(int i = 0; i < used.length; i++){
if(used[i] == false){
used[i] = true;
arrange(res, used, nums, temp);
used[i] = false;
temp.remove(temp.size() - 1);
}
}
return;
}
}``````

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

``````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]){
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));
}
}``````

``````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;
}
}
}
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));
}
}``````