数组全排列算法非递归实现

全排列还是挺有点意思的,看起来很简单,做起来挺复杂的,除了之前的递归方式之外,研究下非递归实现

比如输入数组为arr = {2, 1, 3},那么简单可以通过下面几步计算全排列

1、arr先进行排序,从小到大,排序后{1, 2, 3}

2、从右往左,找到第一个i,使得arr[i] < arr[i+1],那么在arr[i+1:len]里找出一个最小的arr[min] > arr[i],然后交换arr[i]和arr[min],最后从小到大排序arr[i+1:len]如此反复

比如上面列子,流程如下:

1、arr从小到大排序,得到排列[1, 2, 3]

2、arr[2] = 3 > arr[1] = 2,arr[2:3] = 3,因此直接交换arr[2]和arr[1],变成了[1, 3, 2],而arr[2:3]排序也只有一个2,因此得到排列[1, 3, 2]

3、arr[1] = 3 > arr[0] = 1,arr[1:3] = [3, 2],arr[min] = arr[2] = 2, 因此交换arr[0]和arr[2],变成了[2, 3, 1],最后arr[1:3]从小到大排序,得到排列[2, 1, 3]

4、arr[2] = 3 > arr[1] = 1,arr[2:3] = 3,因此直接交换arr[2]和arr[1],变成了[2, 3, 1],而arr[2:3]排序也只有一个1,因此得到排列[2, 3, 1]

5、arr[1] = 3 > arr[0] = 2,arr[1:3] = [3, 1],arr[min] = arr[1] = 3,因此交换arr[0]和arr[1],变成了[3, 2, 1],最后arr[1:3]从小到大排序,得到排列[3, 1, 2]

6、arr[2] = 2 > arr[1] = 1,arr[2:3] = 2,因此直接交换arr[1]和arr[2],变成了[3, 2, 1],而arr[2:3]排序也只有一个1,因此得到排列[3, 2, 1]

综上可以得到全排列包括[1, 2, 3],[1, 3, 2],[2, 1, 3],[2, 3, 1],[3, 1, 2],[3, 2, 1]

从上面结果可以看出还是从小到大的排列,细细体会一下,得到结果的步骤是:

1、首先从小到大排序,能够保证第一个排列是最小的一个排列

2、arr[i]逐渐变大,arr[i+1, len]不停增大,arr[0:i]保持不变

可能数组长度太小,不能看出效果,下面以{1, 2, 3, 4}画出一个完整的过程,红色排列代表输出的一个排列

NewImage

整体实现并没有拆分动作,只是不停地操作nums这个数组,基本都是顺序操作

首先初始nums从小到大排序之后,先添加到list

然后就进行大小判断,得到最小值,交换,逆序,得到新的排列

最终得到全排列,要注意如果nums为空或者一个元素的时候,就直接返回,否则交换就报错了

package com.lihuia.bean;

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

/**
* Copyright (C), 2018-2020
* FileName: Permutation
* Author: lihui
* Date: 2020/1/3
*/

public class Permutation {

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 quickSort(int[] nums, int start, int end) {
int left = start;
int right = end;
int temp;
if (left <= right) {
temp = nums[left];
while (left != right) {
while (left < right && nums[right] >= temp) {
right--;
}
nums[left] = nums[right];
while (left < right && nums[left] <= temp) {
left++;
}
nums[right] = nums[left];
}
nums[right] = temp;
quickSort(nums, start, left - 1);
quickSort(nums, right + 1, end);
}
}

public String toString(int[] nums) {
return Arrays.toString(nums);
}

public void permuteUnique(int[] nums) {
int len = nums.length;
if (len <= 1) {
list.add(toString(nums));
return;
}

quickSort(nums, 0, len - 1);
list.add(toString(nums));

while (true) {
int right = len - 1;
int i;
int min = 0;
for (i = right - 1; i >= 0; i--) {
if (nums[i] < nums[i + 1]) {
min = i;
break;
} else if (i == 0) {
return;
}
}
for (i = right; i >= 0; i--) {
if (nums[i] > nums[min]) {
break;
}
}
swap(nums, min, i);
quickSort(nums, min + 1, right);
list.add(toString(nums));
}
}

public String getPermute(int[] nums, int index) {
permuteUnique(nums);
System.out.println(list.size());
return list.get(index);
}
}

还有一个问题,就是假如有重复元素,比如arr={2, 1, 2},那么

首先排序变成[1, 2, 2]

然后2 > 1,因此1和2交换,但是由于遍历的时候是从右往左遍历,上面死循环里第二个for循环,从右往左找到了第一个i是的nums[i] > nums[min],也就是此时的nums[2] = 2 > nums[0] = 1,所以更换后是[2, 2, 1],逆序后[2, 1, 2]输出

接着2 > 1,直接交换nums[1]和nums[2],[2, 2, 1]输出

因此得到了[1, 2, 2],[2, 1, 2],[2, 2, 1]全排列,可见并不会出现重复的排列,原因就是比较的时候,只有大小关系,没有相等的关系,以及在交换的时候,只会和右边最小的一个比nums[min]大的值交换

OVER

发表评论