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

by

2020-01-03

23:04:36

Leave a comment on 数组全排列算法非递归实现

Java

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

比如输入数组为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

发表回复