全排列笔记
14天阅读挑战赛
全排列
题目
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [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;
}
运行结果
