数组全排列算法递归处理

原题是提供一个数组,列出所有数字组成的全排列,排序后,进而随便提供一个index,能够逆向输出第index个排列

比如数组nums={1, 2, 3},那么全排列排序后结果为:[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

因此,完成流程有三个步骤:

1、nums求全排列

2、全排列排序保存起来

3、返回倒数index个数据

这是一种递归,比如上面的{1, 2, 3},所有的全排列就是【1开头+(2, 3)全排列】+【2开头+(1,3)全排列】+【3开头+(1,2)全排列】,进而继续分拆,最终只有一个数字的时候

先简单画一个图

NewImage

大致流程:

1、遍历nums,将每个数字作为首元素,剩下的部分全排列

2、(1)当首元素是nums[i]=nums[0]=2,nums[0]=2和nums[0]=2交换,这里没变化,去掉nums[0]右移一位递归,继续nums[0]=1和nums[0]=1交换,没变化,去掉nums[0]右移一位递归,继续nums[0]=4和nums[0]=4交换,没变化,去掉nums[0]右移一位递归,此时就剩下一个元素3,nums[left]=nums[right],这就是递归结束条件,就返回此刻的排列2143,第一行红色排列,虽然这种情况下没变化,但是需要将交换过的数字换回来,因为每一步子数组全排列都是基于相同的父数组来进行遍历

(2)上面第一行红色排列结束后,回到{4,3}分拆的地方,此时就要换首位,也就是4和3交换,即nums[0]=4和nums[i]=3交换,此时由于for循环的缘故i是1,交换后就生成了新的排列2134;这个时候再将nums[0]=4和nums[i]=3换回来,这样分拆前数组还是143

(3)恢复了原样才能继续更外层的循环,1和4交换,原始数组变成了413,进而继续进行上面(1)(2)两步,可以得到2413和2431两个排列

(4)上层恢复了原样,更外层就恢复成了原始的2143,这样才能继续外层交换,2和1交换,最外层数组变成了1243,继续进行上面(1)(2)(3)

写得有点迷糊,说实话debug一把也看得有些晕,说到底还是自身递归能力不强,缺少那种感觉,可以自行研究

上面已经知道了递归的结束条件是最终分裂仅有一个元素的时候,也就是nums[left]==nums[right],这时候就可以保存整个排列了,可以将数组变成字符串保存在一个List<String>里,最终是要从小到大排序后,输出倒数第index个排列,那么可以将List先排个序然后做一个翻转(这应该不是考察点),获取第index个排列即可

简单Java代码

package com.lihuia.bean;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
* Copyright (C), 2018-2019
* FileName: Permutations
* Author: lihui
* Date: 2019/12/25
*/

public class Permutations {

private List<String> list = new ArrayList<>();

public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}

public void permuteUnique(int[] nums, int left, int right) {
if (left == right) {
list.add(Arrays.toString(nums));
} else {
for (int i = left; i <= right; i++) {
swap(nums, left, i);
permuteUnique(nums, left + 1, right);
swap(nums, left, i);
}
}
}

public String getPermute(int[] nums, int index) {
int length = nums.length;
permuteUnique(nums, 0, length - 1);
Collections.sort(list);
Collections.reverse(list);
return list.get(index);
}
}

可以查看下结果:

全排列:    [[2, 1, 4, 3], [2, 1, 3, 4], [2, 4, 1, 3], [2, 4, 3, 1], [2, 3, 4, 1], [2, 3, 1, 4], [1, 2, 4, 3], [1, 2, 3, 4], [1, 4, 2, 3], [1, 4, 3, 2], [1, 3, 4, 2], [1, 3, 2, 4], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 2, 1], [4, 3, 1, 2], [3, 1, 4, 2], [3, 1, 2, 4], [3, 4, 1, 2], [3, 4, 2, 1], [3, 2, 4, 1], [3, 2, 1, 4]]
从小到大: [[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]]
从大到小: [[4, 3, 2, 1], [4, 3, 1, 2], [4, 2, 3, 1], [4, 2, 1, 3], [4, 1, 3, 2], [4, 1, 2, 3], [3, 4, 2, 1], [3, 4, 1, 2], [3, 2, 4, 1], [3, 2, 1, 4], [3, 1, 4, 2], [3, 1, 2, 4], [2, 4, 3, 1], [2, 4, 1, 3], [2, 3, 4, 1], [2, 3, 1, 4], [2, 1, 4, 3], [2, 1, 3, 4], [1, 4, 3, 2], [1, 4, 2, 3], [1, 3, 4, 2], [1, 3, 2, 4], [1, 2, 4, 3], [1, 2, 3, 4]]
倒数第四: [4, 2, 1, 3]

 

到这里其实还没有结束,假如传入的nums里面有重复的元素,因为是存放在ArrayList里,肯定会有重复的排列,最后输出的结果肯定不准,因此可以最后做一下处理,直接lambda表达式stream去重下返回即可

package com.lihuia.bean;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
* Copyright (C), 2018-2019
* FileName: Permutations
* Author: lihui
* Date: 2019/12/25
*/

public class Permutations {

private List<String> list = new ArrayList<>();

public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}

public void permuteUnique(int[] nums, int left, int right) {
if (left == right) {
list.add(Arrays.toString(nums));
} else {
for (int i = left; i <= right; i++) {
swap(nums, left, i);
permuteUnique(nums, left + 1, right);
swap(nums, left, i);
}
}
}

public String getPermute(int[] nums, int index) {
int length = nums.length;
permuteUnique(nums, 0, length - 1);
Collections.sort(list);
Collections.reverse(list);
return list.stream().distinct().collect(Collectors.toList()).get(index);
}
}

大部分基本参考google,然后自己体会总结,网上做法很多,但递归方式基本差不多

OVER

发表评论