全排列

2020-05-14

全排列问题

LeetCode 46、全排列 https://leetcode-cn.com/problems/permutations/

题目的意思非常简单，给定我们一个序列，并且没有重复元素 让我们返回所有的全排列.
说到全排列，一般有两种实现方式，我们从中学就学过排列组合的知识.
例如给定我们 1 2 3 即一共有六种排列方式，（n!）这在我们中学就知道了.
现在有一种简单的实现方案，当第一个位置为1时，此时将后面2个数字做全排列.然后此时我们交换位置，让2去前面，然后将后面两个数字做全排列…….
这时候我们就会发现，每个数字都会在队头出现一次，然后将后面的元素做全排列.
很明显这是一个递归算法，接下来我们来实现一下.

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        if(nums.length==0) return res;
           dfs(nums,0);
        return res;
    }
    private void dfs(int[]nums,int k){
       
        if(k==nums.length){
            //将数组转换为list集合
           res.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
        }
        //将每一个元素都放到第一个，然后递归，将后面的元素进行全排列
        for(int i=k;i<nums.length;i++){
            //与第一个位置的元素交换
            swap(nums,i,k);
            //后面的元素继续全排列
            dfs(nums,k+1);
            //还原
            swap(nums,i,k);
            
        }
    }
    private void swap(int[]nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}

接下来我们来看另外一道题目

LeeCode 47 全排列2、https://leetcode-cn.com/problems/permutations-ii/

本题我们还是可以利用刚才的思路，将每一个元素都放在首位，然后将后面的进行全排列，但是此时里面是含有重复元素的，如果我们按照这个思路，最后返回的结果里面应该会有很多重复的结果.
说到去重，最常见的就是利用Set集合，本身Set集合就是一个不包含重复元素的集合.但是其效果并不是很高，但是实现思路很简单，我们首先先实现利用Set集合去重的方案

class Solution {
    Set<List<Integer>>set=new HashSet<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums.length==0) return new ArrayList<>();
          dfs(nums,0);
      List<List<Integer>> res=new ArrayList<>(set);
      
        return res;
    }
    private void dfs(int[]nums,int k){
        if(k==nums.length){
            List<Integer>list=new ArrayList<>();
            for(int num:nums){
                list.add(num);
            }
             set.add(list);
        }  
        for(int i=k;i<nums.length;i++){
            swap(nums,i,k);
            dfs(nums,k+1);
              swap(nums,i,k);
        }
    }
    private void swap(int[]nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
    
}

但是上面的实现方案效率比较低，接下来我们介绍另外一种思路。利用回溯的思想。

其实回溯就是遍历一棵决策树，接下来我们可以画出这棵决策树。

决策树

即我们就是在做选择，这是一个典型的回溯思想，我们可以利用dfs+回溯来实现下面这个过程

首先还是先解决一个问题，不带重复数字的全排列.

class Solution {
     List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
            if(nums.length==0) return res;
        boolean []vis=new boolean[nums.length];
        dfs(nums,0,new ArrayList<>(),vis);
        return res;
    }
    private void dfs(int[]nums,int pos,List<Integer>list,boolean[]vis){
        if(pos==nums.length){
            res.add(new ArrayList<>(list));
          return;
        }
        //做选择
        for(int i=0;i<nums.length;i++){
            if(vis[i]==false){
                list.add(nums[i]);
                //做标记
                vis[i]=true;
                dfs(nums,pos+1,list,vis);
                //撤销选择
                list.remove(list.size()-1);
              //重置标记过的元素
                vis[i]=false;
            }
        }
    }
}

根据上面的思路，我们可以很简单的实现全排列.重点就在于撤销选择这个回溯过程。一定不要忘记把标记过的元素重置

事实上，上述中的pos 其实就是表明一共选择了几个元素，我们也可以不定义这个变量，仅仅只靠list集合中的元素个数也可以完成该过程

class Solution {
     List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
            if(nums.length==0) return res;
        boolean []vis=new boolean[nums.length];
        dfs(nums,new ArrayList<>(),vis);
        return res;
    }
    private void dfs(int[]nums,List<Integer>list,boolean[]vis){
        if(list.size()==nums.length){
            res.add(new ArrayList<>(list));
          return ;
        }
        //做选择
        for(int i=0;i<nums.length;i++){
            if(vis[i]==false){
                list.add(nums[i]);
                //做标记
                vis[i]=true;
                dfs(nums,list,vis);
                //撤销选择
                list.remove(list.size()-1);
               vis[i]=false;
            }
        }
    }
}

事实上，我更倾向于定义pos这个变量，因为可以让整个过程变得更加清晰明了.

接下来我们来实现带有重复的全排列过程

首先明确一点，如果我们不利用set集合，该如何去除重复元素.
这里提供一个思路，首先我们要保证两个相等的元素必须在一起，因此我们对整个数组进行排序.
并且我们要定义一个规则：如果出现两个相等的元素，我们默认为选择第一个元素. 例如 1 1 2 我们默认选择第一个2，当然还有另外一种可能，就是112 ，即这两个1我们都选.
那么很明显，当我们第一个1不选的时候，后一个1也不能选.

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
         if(nums.length==0) return res;
        //一定不要忘了排序
        Arrays.sort(nums);
        boolean[]vis=new boolean[nums.length];
        dfs(nums,0,new ArrayList<>(),vis);
        return res;
    }
    private void dfs(int[]nums,int pos,List<Integer>list,boolean[]vis){
        if(pos==nums.length){
            res.add(new ArrayList<>(list));
            return ;
        }
        for(int i=0;i<nums.length;i++){
            //如果是一个元素，我们当然可以选，如果相邻两个元素不相等我们也可以选
            //最后一种情况就是如我们所说的，如果两个元素相等，
            //并且第一个元素选了，我们才能选择第二个
            if(vis[i]==false&&(i==0||nums[i-1]!=nums[i]||vis[i-1]==true)){
                list.add(nums[i]);
                vis[i]=true;
                dfs(nums,pos+1,list,vis);
                vis[i]=false;
                list.remove(list.size()-1);
                
            }
        }
    }
}

通过这个方法，我们可以极大的提高效率.通常来说，我们经常会将dfs和回溯这两个方法结合一起使用.其实全排列问题实际上也可以归类于搜索问题，相信看到这里，你对全排列也有了一个更深的印象.