全排列笔记

举报
海轰Pro 发表于 2022/10/22 22:10:44 2022/10/22
【摘要】 46. 全排列题目给定一个 没有重复 数字的序列,返回其所有可能的全排列。示例:输入: [1,2,3]输出:[  [1,2,3],  [1,3,2],  [2,1,3],  [2,3,1],  [3,1,2],  [3,2,1]]解答方法一:回溯思路 从高中的数学知识我们可以知道从[1,2,3]中选出3个数进行排列(排序有顺序之分、组合没有顺序之分)结果有n!=3!=3*2*1种1-2-31...

46. 全排列

题目

给定一个 没有重复 数字的序列,返回其所有可能的全排列。

示例:

输入: [1,2,3]

输出:

[

 [1,2,3],

 [1,3,2],

 [2,1,3],

 [2,3,1],

 [3,1,2],

 [3,2,1]

]


解答

方法一:回溯

思路

从高中的数学知识我们可以知道

从[1,2,3]中选出3个数进行排列(排序有顺序之分、组合没有顺序之分

结果有n!=3!=3*2*1种

1-2-3

1-3-2

2-1-3

2-3-1

3-1-2

3-2-1

怎么计算的呢?

假设现在我们有三个数:1、2、3

需要依次填入下面三个蓝色方块

那么第一个方块有三种选择:1或2或3

第二个有两种选择:2或者3(假设第一次选择了1)

那么第三个方块就只有一种选择:3(假设第一次选择1,第二次选择2)

综上:n个数(不重复),填入n个方块,一共有n!种不同排列方式。


那么为什么第一次有三种而第二次只有两种了呢?

这是因为第一次选择时,没有一个数被选,那么一个三个数,就有三种选择方法

到第二次选择时,因为第一次必定选择了一个数,这时剩下的可供选择的数就只有2个,选择就只有两种了

到第三次选择时,因为前面两次已经选择了两个数,可供选择的数就只有一个,选择就只有一种了


从上面提取核心思想:

每次进行选择时,我们都是从一些尚未选择的数中选择出一个数字填充方块,然后将该数标记为已选择,再进行下一轮新的选择。


根据上述思想,画出下面思路图:

上图若没有理解 没有关系 先看下面


这里我们可以利用一个全局变量temp数组,初始化为空,作为一个临时容器

开始时,1、2、3都是尚未选择的

此时我们可以选择 1 或 2 或 3,有三种选择方法

假设我们选择了1后

那么将1添加至temp中【temp:1】

此时1已经被选择

之后可供我们选择的就是 2、3

再选择2【temp:1-2】

最后再选择3【temp:1-2-3】

此时temp与我们预期的答案吻合【其实就是temp数组的长度与预期结果数组长度一样】

将其添加至res结果数组中即可


在我们的思想中

可以很简单的知道 1被选择 2、3未被选择

但是在程序中,我们如何实现这个呢?


这里我们利用一个数组isused来判定元素是否被选择

假如情况是:1被选择 2、3未被选择

那么原数组与isused数组关系如下:

所以在每次进行选择前,我们利用isused数组,判定某个元素是否被选择

只有未被选择 我们才可以对这个元素进行操作


所以在每次选择前,我们都会扫描isused数组,当为true时,才对该元素进行操作。【具体是true还是false进行操作依据个人习惯而定,这里海轰是true代表未被选择】


根据上面的思路,写出下面的代码:

vector<int> temp;
void backtracking(vector<vector<int>> &res,vector<bool> &isused,vector<int> &nums){
        // 当temp数组的长度等于期望数组的长度时 return
        if(temp.size()==nums.size()){
            res.push_back(temp);
            return ;
        }
        // 遍历所有选择
        for(int i=0;i<nums.size();++i){
            // 对没有选择过的元素再进行抉择:选择它|不选择它
            if(isused[i]){
            		// 选择该元素 选择后标记该元素为已选择 同时进行下一元素的抉择
                temp.push_back(nums[i]);
                isused[i]=false;
                backtracking(res,isused,nums);
                // 回复原来状态:未选择 同时从temp中pop出 
                isused[i]=true;
                temp.pop_back();
          }
   }
}
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        vector<bool> isused(nums.size(),true);
        backtracking(res,isused,nums);
        return res;
}

运行结果

疑问

疑问1:程序具体是怎么执行的呢?

这里只给出程序的运行简图,

对详细步骤感兴趣对小伙伴可以自己动手画画步骤图

疑问2:为什么当 temp.size()==nums.size()或所有的元素都被选择后 函数backtracking返回呢?

首先

当temp.size()==nums.size()时

代表此时的temp已经满足答案需要

可以将其添加至res中


如果temp.size()<nums.size()

那么意思就是还temp中还需要一些元素

比如要求数组长度是4

此时temp长度只有2

那么就还需要再选择两个数进入temp


其次

所有的元素都被选择后

说明已经没有元素可以供加入temp中

则必须return


疑问3:为什么 backtracking函数的开头就需要判定temp.size()==nums.size()?而不是在函数中部或者尾部?

首先可以看出

在这里我们用了递归

那么必须要一个递归终止条件

不然递归怎么结束呢?


backtracking作为一个递归函数

我们可以想到

每次进入backtracking函数时

第一要务就是需要判定此时temp的size

如果满足答案要求的长度

将temp压入res数组

再return

后面步骤也就不需要再运行


疑问4:为什么backtracking函数中每次要进行for(int i=0;i<nums.size();++i){}循环?

这里是因为每次进行抉择前

我们需要找出所有未被选择的元素

在这里我们使用的判定数组isused标志选择与否

所以每次都需要循环扫描isused数组【代码中:因为isused数组长度与nums数组一样,这里size写谁都可以】


疑问5:为什么会进行temp.pop_back()?

从代码中

我们可以发现

temp.pop_back()前面有句 backtracking(res,isused,nums,temp);


也就是说

只有backtracking(res,isused,nums,temp) 运行完后

才会进行temp.pop_back()


那么啥时候backtracking(res,isused,nums,temp)会结束呢?

参考疑问2

可以知道

backtracking(res,isused,nums,temp)结束时

代表某个元素已经被选择了,且引进被压入了temp中使用了

额外意思就是该元素已经被使用了


因为每次抉择都有两种:选择与不选择

那么选择结束了

之后肯定就是不选择了

但是此时元素已经被压入了temp中

那么需要怎么办呢?

简单,pop出即可,同时标记isuserd数组为true即可。


改进

改进方案:temp可以不定义为全局变量

代码如下:

void backtracking(vector<vector<int>> &res,vector<bool> &isused,vector<int> &nums,vector<int> &temp){
        // 选择完毕
        if(temp.size()==nums.size()){
            res.push_back(temp);
            return ;
        }
        for(int i=0;i<nums.size();++i){
            if(isused[i]){
                temp.push_back(nums[i]);
                isused[i]=false;
                backtracking(res,isused,nums,temp);
                isused[i]=true;
                temp.pop_back();
            }
    }
}
vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        vector<bool> isused(nums.size(),true);
        vector<int> temp;
        backtracking(res,isused,nums,temp);
        return res;
}

运行结果

改进方案:bool<->int push_back<->emplace_back

isused数组海轰使用的bool变量

在评论区有小伙伴说

当数据量大的时候使用int类型会好一点

同时

在将temp压入res时

使用emplace_back()会好一点

因为不会产生临时变量


代码如下:

vector<int> temp;
    void backtracking(vector<vector<int>> &res,vector<int> &isused,vector<int> &nums){
        // 当temp数组的长度等于期望数组的长度时 return
        if(temp.size()==nums.size()){
            res.emplace_back(temp);
            return ;
        }
        // 遍历所有选择
        for(int i=0;i<nums.size();++i){
            // 对没有选择过的元素再进行抉择:选择它|不选择它
            if(!isused[i]){
            		// 选择该元素 选择后标记该元素为已选择 同时进行下一元素的抉择
                temp.push_back(nums[i]);
                isused[i]=1;
                backtracking(res,isused,nums);
                // 回复原来状态:未选择 同时从temp中pop出 
                isused[i]=0;
                temp.pop_back();
          }
   }
}
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        vector<int> isused(nums.size());
        backtracking(res,isused,nums);
        return res;
}

运行结果

方式二:回溯(官方题解,动态交换原数组中的元素)


官方题解代码如下:

void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
        // 所有数都填完了
        if (first == len) {
            res.emplace_back(output);
            for(int i=0;i<output.size();++i){
                cout<<output[i]<<" ";
            }
            cout<<endl;
            return;
        }
        for (int i = first; i < len; ++i) {
            // 动态维护数组
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);
            // 撤销操作
            swap(output[i], output[first]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }

运行结果

思路

在官方题解中

并没有向我们使用的依次将元素添加至一个临时数组temp中

而是直接在原数组上进行变换

将变换结果依次加入结果数组res中。


程序具体执行过程如下:

观察每个节点生成的下一个节点,元素是如何交换的?


对for循环进行思考:

当first=0时,此时for循环会进行:swap(nums[0],nums[0])/swap(nums[1],nums[0])/swap(nums[2],nums[0])

当first=1时,此时for循环会进行:swap(nums[1],nums[1])/swap(nums[2],nums[1])

当first=2时,此时for循环会进行:swap(nums[2],nums[2])

        for (int i = first; i < len; ++i) {
            // 动态维护数组
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);// 注意:这里是first+1
            // 撤销操作
            swap(output[i], output[first]);
        }


这里可能会有点难度

不好想象程序时如何进行的?

建议首先自己对照程序跑一次

明白每一次运行的结果

然后再对照上面几张图寻找规律

之后对官方题解就会有所理解了


变式

从[1,2,3,4,5,6]中,选择3个数进行排列,输出所有排列方式。

代码(修改backtracking函数中的返回条件即可)

vector<int> temp;
    void backtracking(vector<vector<int>> &res,vector<bool> &isused,vector<int> &nums){
        // 选择完毕 
        if(temp.size()==3){
            res.push_back(temp);
            return ;
        }
        for(int i=0;i<nums.size();++i){
            if(isused[i]){
                temp.push_back(nums[i]);
                isused[i]=false;
                backtracking(res,isused,nums);
                isused[i]=true;
                temp.pop_back();
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        vector<bool> isused(nums.size(),true);
        backtracking(res,isused,nums);
        return res;
    }

运行结果

代码2(对官方题解进行修改):

void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
        // 所有数都填完了
        // 修改结束条件
        if (first == 3) {
            vector<int> temp(output.begin(),output.begin()+3);//利用临时数组存储
            res.emplace_back(temp);
            return;
        }
        for (int i = first; i < len; ++i) {
            // 动态维护数组
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);
            // 撤销操作
            swap(output[i], output[first]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }

运行结果

【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。