[LeetCode] Permutations 全排列

落日映苍穹つ 2022-04-14 03:24 188阅读 0赞

Given a collection of numbers, return all possible permutations.

For example,  
`[1,2,3]` have the following permutations:  
`[1,2,3]`, `[1,3,2]`, `[2,1,3]`, `[2,3,1]`, `[3,1,2]`, and `[3,2,1]`.

**图形化表述:**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70][]

解释：当第一次得到\[1,2,3\]时，此时执行了递归终止条件，在终止条件中将此结果保存下来 ，然后内嵌的generatePermutation函数执行结束，返回到上一层递归(return)，在返回过程中也做了额外的操作， 就是删除了末尾的数字3 和 将数字3标示为未使用

注意： 内嵌的generatePermutation函数是留给上一层递归进行操作

**表达式表述:**

![20181123175432591.png][]

## java算法: ##

import java.util.List;
    import java.util.ArrayList;
    import java.util.LinkedList;
    
    public class liubobo_8_2 {
    
        private ArrayList<List<Integer>> res;
        private boolean[] used;//辅助数组,代表数组中的i元素是否被使用过了
    
        public List<List<Integer>> permute(int[] nums) {
    
            res = new ArrayList<List<Integer>>();
            if(nums == null || nums.length == 0)//如何测试数据为空,则直接返回空
                return res;
    
            used = new boolean[nums.length];//初始化used,数组让长度由用户输入的数字长度决定
            LinkedList<Integer> p = new LinkedList<Integer>();
            generatePermutation(nums, 0, p);
    
            return res;
        }
    
        // p中保存了一个有index-1个元素的排列。
        // 向这个排列的末尾添加第index个元素, 获得一个有index个元素的排列
        private void generatePermutation(int[] nums, int index, LinkedList<Integer> p){
    
            if(index == nums.length){//递归终止条件
                res.add((LinkedList<Integer>)p.clone());
                return;
            }
    
            for(int i = 0 ; i < nums.length ; i ++)
                if(!used[i]){//元素userd[i]没有被使用
                    used[i] = true;//使用了第i个元素
                    p.addLast(nums[i]);
                    generatePermutation(nums, index + 1, p );
                    p.removeLast();//删除最后的元素,这是题目性质问题,所谓的元素间在打仗
                    used[i] = false;//注意实际元素数组是和userd[]数组绑定的,所以删除也要同时处理
                }
    
            return;
        }
    
        private static void printList(List<Integer> list){
            for(Integer e: list)
                System.out.print(e + " ");
            System.out.println();
        }
    
        public static void main(String[] args) {
    
            int[] nums = {1, 2, 3};
            List<List<Integer>> res = (new liubobo_8_2()).permute(nums);
            for(List<Integer> list: res)
                printList(list);
        }
    }

# #

本题的难度：

1.如何定义最后的返回数据结构， 这里使用了

static ArrayList<List<Integer>> res;

实例化：

res= new ArrayList<List<Integer>>();

2.在终止条件中，为了保存结果值， 使用

if(result.size()==s.length){
        res.add((LinkedList<Integer>)result);
    }

得到的结果是：

![20181128173447542.png][]

正确的是：

if(result.size()==s.length){
        res.add((LinkedList<Integer>)result.clone());
    }

结果是：

![20181128173519101.png][]

## 感受: ##

**这道题相比  Letter conbinations of a phone number 不一样的地方, 可以从图形化树上看出来 , 下面沾下上一个问题的图形化树图:**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 1][]

**发现本题问题中元素是出现"冲突"的, 所以较上一个问题稍难点, 但思想都是一样的(回溯)**

## **同时比较核心代码共性:** ##

**Permutations:**

private void generatePermutation(int\[\] nums, int index, LinkedList<Integer> p)\{

if(index == nums.length)\{//递归终止条件  
            res.add((LinkedList<Integer>)p.clone());  
            return;  
        \}

for(int i = 0 ; i < nums.length ; i ++)  
            if(!used\[i\])\{//元素userd\[i\]没有被使用  
                used\[i\] = true;//使用了第i个元素  
                p.addLast(nums\[i\]);  
                generatePermutation(nums, index + 1, p );  
                p.removeLast();//删除最后的元素,这是题目性质问题,所谓的元素间在打仗  
                used\[i\] = false;//注意实际元素数组是和userd\[\]数组绑定的,所以删除也要同时处理  
            \}

return;  
    \}

**Letter conbinations of a phone number:**

private void findCombination(String digits, int index, String s)\{  
    if(index == digits.length())\{//递归终止条件  
        res.add(s);  
        return;  
    \}  
    String letters = letterMap\[digits.charAt(index) - '0'\];  
    for(int i = 0 ; i < letters.length() ; i ++)\{   
        findCombination(digits, index+1, s + letters.charAt(i));  
    \}  
    return;  
\}

通过比较发现,基本绝大多数代码都是语义一致的, 只是前者使用了辅助数组, 让问题解决稍麻烦了点

# #

## 下面是其他博主的对此问题的看法: ##

这道题是求全排列问题，给的输入数组没有重复项，这跟之前的那道[ Combinations 组合项][Combinations] 和类似，解法基本相同，但是不同点在于那道不同的数字顺序只算一种，是一道典型的组合题，而此题是求全排列问题，还是用递归DFS来求解。这里我们需要用到一个visited数组来标记某个数字是否访问过，然后在DFS递归函数从的循环应从头开始，而不是从level开始，这是和[ Combinations 组合项][Combinations] 不同的地方，其余思路大体相同，代码如下：

解法一

class Solution {
    public:
        vector<vector<int> > permute(vector<int> &num) {
            vector<vector<int> > res;
            vector<int> out;
            vector<int> visited(num.size(), 0);
            permuteDFS(num, 0, visited, out, res);
            return res;
        }
        void permuteDFS(vector<int> &num, int level, vector<int> &visited, vector<int> &out, vector<vector<int> > &res) {
            if (level == num.size()) res.push_back(out);
            else {
                for (int i = 0; i < num.size(); ++i) {
                    if (visited[i] == 0) {
                        visited[i] = 1;
                        out.push_back(num[i]);
                        permuteDFS(num, level + 1, visited, out, res);
                        out.pop_back();
                        visited[i] = 0;
                    }
                }
            }
        }
    };

还有一种递归的写法，更简单一些，这里是每次交换num里面的两个数字，经过递归可以生成所有的排列情况，代码如下：

解法二

class Solution {
    public:
        vector<vector<int> > permute(vector<int> &num) {
            vector<vector<int> > res;
            permuteDFS(num, 0, res);
            return res;
        }
        void permuteDFS(vector<int> &num, int start, vector<vector<int> > &res) {
            if (start >= num.size()) res.push_back(num);
            for (int i = start; i < num.size(); ++i) {
                swap(num[start], num[i]);
                permuteDFS(num, start + 1, res);
                swap(num[start], num[i]);
            }
        }
    };

最后再来看一种方法，这种方法是CareerCup书上的方法，也挺不错的，这道题是思想是这样的：

当n=1时，数组中只有一个数a1，其全排列只有一种，即为a1

当n=2时，数组中此时有a1a2，其全排列有两种，a1a2和a2a1，那么此时我们考虑和上面那种情况的关系，我们发现，其实就是在a1的前后两个位置分别加入了a2

当n=3时，数组中有a1a2a3，此时全排列有六种，分别为a1a2a3, a1a3a2, a2a1a3, a2a3a1, a3a1a2, 和 a3a2a1。那么根据上面的结论，实际上是在a1a2和a2a1的基础上在不同的位置上加入a3而得到的。

\_ a1 \_ a2 \_ : a3a1a2, a1a3a2, a1a2a3

\_ a2 \_ a1 \_ : a3a2a1, a2a3a1, a2a1a3

解法三:

class Solution {
    public:
        vector<vector<int> > permute(vector<int> &num) {
            if (num.empty()) return vector<vector<int> >(1, vector<int>());
            vector<vector<int> > res;
            int first = num[0];
            num.erase(num.begin());
            vector<vector<int> > words = permute(num);
            for (auto &a : words) {
                for (int i = 0; i <= a.size(); ++i) {
                    a.insert(a.begin() + i, first);
                    res.push_back(a);
                    a.erase(a.begin() + i);
                }
            }   
            return res;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70]: /images/20220414/31c157c38c71447ebe349f9bad02502f.png
[20181123175432591.png]: /images/20220414/47a7949153064629972727436e32ca48.png
[20181128173447542.png]: /images/20220414/7837e4ceb5554cc98e66f8b7a74c9489.png
[20181128173519101.png]: /images/20220414/afe2ebdf03264ce3b6e9c20ab5a967cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 1]: /images/20220414/d5ad92a77c12441694bac7890714b4f4.png
[Combinations]: http://www.cnblogs.com/grandyang/p/4332522.html