全排列算法(不含重复元素)

背景

全排列是一个比较经典和常见的问题，一些较大的公司可能会喜欢问这种经典算法问题。我希望通过这个博客来加深对全排列算法的理解，同时也归纳一下有多少种全排列的实现方法
注意：本篇博客讨论的是无重复元素的全排列算法

递归算法

说到全排列实现算法，最简单最容易让人想到的就是递归

递归思路

我们知道全排列的含义就是一个序列所有排序的可能性。我们可以用分治的思路来理解全排列
假设有一个序列S[0..n-1]，那么它的全排列可以这样理解
如果第一个元素是S[0]，那么如果可以得到其余元素的全排列，就得到了当S[0]成为第一个元素时的所有排列可能
如果第一个元素是S[1]，那么如果可以得到其余元素的全排列，就得到了当S[1]成为第一个元素时的所有排列可能
……
于是我们得到了全局解，所有元素的全排列。

仔细观察，我们发现求S[1..n-1]的全排列与求S[0..n-1]全排列性质相同，只是规模变小了而已，于是递归即可得到答案。

代码

 public  List<List<Integer>> permute(int[] nums) {
         return permute(nums,0,nums.length-1);
    }

    /**
     * 对[start,end]进行全排列，并返回这个全排列
     *
     * @param nums
     * @param start
     * @param end
     * @return
     */
    public List<List<Integer>> permute(int[] nums,int start,int end) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> permute = new ArrayList<Integer>();
        if(start == end){
            //一次全排列

            for(int i = 0;i<nums.length;i++){
                permute.add(nums[i]);
            }
            result.add(permute);
            return result;
        }
        //固定住左边第一个,也就是固定住start
        int fixed = start;
        for(int i = fixed;i<=end;i++){
            move(nums,fixed,i);//交换
            result.addAll(permute(nums,fixed+1,end));  //全排列
            move(nums,fixed,i);
        }
        return result;
    }

    private static void move(int[] nums,int a,int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

非递归算法

在没有相同元素的情况下，任意两个不同排列构成的数是不可能相同的，也即有大有小，那么如果我们能按照大小关系，找到某一个排列的下一个排列，就能得到全排列。下一个排列就是刚好大于原排列的排列，即原排列A的下一个排列B的充分必要条件是A<B且不存在一个排列C使得A<C<B。
找到某一个排列的下一个排列，可以参考LeetCode上的一道题目:https://leetcode-cn.com/problems/next-permutation/description/

非递归思路

基本思想已经成型了
1、对所有元素从小到大排序，得到排列A
2、寻找排列A的下一个排列B，满足B>A且中间找不到一个排列C使得B>C>A
3、重复步骤2，如果再也找不到下一个排列，结束搜索

代码

public  static List<List<Integer>> permute2(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();//结果

        //从小到大排序
        Arrays.sort(nums);
        //一次排列
        result.add(onePermute(nums));

        boolean hasNext = nextPermutation(nums);
        while(hasNext){
            //一次排列
            result.add(onePermute(nums));

            //获取下一次
            hasNext = nextPermutation(nums);
        }
        return result;
    }

    private static List<Integer> onePermute(int[] nums){
        List<Integer> permute = new ArrayList<Integer>();
        //一次排列
        for(int i = 0;i<nums.length;i++){
            permute.add(nums[i]);
        }
        return permute;
    }

    /**
     * 使用下一个排列的非递归解来解全排列这道题
     *
     * @param nums
     * @return  true 除了本解，是否还有下一个排列
     */
    public static boolean nextPermutation(int[] nums) {

        //异常处理 - 只有1个数字或没有数字的时候
        if(nums == null || nums.length <=1){
            return false;
        }


        int last = nums[nums.length-1];
        int index = nums[nums.length-2];
        if(nums[nums.length -1] > nums[nums.length -2]){
            last = nums[nums.length-2];
            nums[nums.length-2] = nums[nums.length-1];
            nums[nums.length -1] = last;
            return true;
        }

        //找连续递增序列的头部
        int pos= nums.length-2;
        while(index >= last && --pos >= 0){
            last = index;
            index = nums[pos];
        }


        if(pos == -1){
            //已经没有下一个解了
            return false;
        }


        //获取连续递增的前面的数
        int number = nums[pos];//pos位置是连续递增的前面的数的位置

        //找到递增序列中比numbers大的最小数................
        int i = 0;
        for(i=nums.length-1;i>pos;i--){
            if(nums[i] > number){
                break;
            }
        }

        //交换
        last = number;
        nums[pos] = nums[i];
        nums[i] = last;

        //从小到大排序
        Arrays.sort(nums,pos+1,nums.length);
        return true;
    }