全排列问题（不含有相同元素与含有相同元素的全排列问题） Leetcode

1.给定一个数组，数组中元素均不相同，写出数组元素的全排列组合

比如： [1,2,3] Output: [ [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]的全排列,很明显是2,3 和3,2，分别以2开头和3开头
然后看[1,2,3]的全排列，分别为1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们是以1开头和2,3全排列的组合，
以2开头1,3,全排列的组合，以3开头1,2,全排列的组合
也就是说我们可以将三个数的全排列问题转化为两个数的全排列问题，方法是：将数组中的每一个数均与数组的第一位的数进行交换，然后对剩下的数进行全排列；每一次交换后要交换回去，因为每一次都是在[1,2,3]的基础上进行的
以[1,2,3]为例就是，数组中的每一个元素都与第一为元素进行交换，1与第一位元素交换，得1,2,3；然后交换回去，为下一次交换做准备
2与第一位元素交换，得2,1,3；
3与第一位元素交换，得3,2,1；
然后对于得到1,2,3；2,1,3；3,2,1问题就可以缩减为除去第一位后2,3； 1,3； 2,1的全排列，然后与第一位组合
而对于2,3的全排列，也可以使用同样的方法，分别将元素2,3与第一位元素进行交换，继续缩减问题，转化为1个元素的全排列问题，对于2,3就是2,3；3,2；然后转化为单元素3和2的全排列问题

1,2,3//原问题 /|\ 1,2,32,1,33,2,1//遍历数组将数组元素分别与第一位元素交换，缩减问题为两个数的全排列问题,将问题缩减为了[2,3]; [1,3]; [2,1]的全排列问题 /\/\/\ 1,2,31,3,22,1,32,3,1 3,2,13,1,2 //遍历数组[2,3]，将数组元素分别与第一位元素交换，将问题缩减为1个数的全排列问题，即将问题缩减为[2]和[3]的全排列问题；其他数组[1,3]; [2,1]类似处理 |||||| 1,2,31,3,22,1,32,3,1 3,2,13,1,2 //可以继续这一步，也可以不继续，就是i = nums.size() 和nums.size()-1的区别所以明显看出可以用深度优先搜索解决，因为每一步所做的处理是相同的

class Solution { public: vector> permute(vector& nums) { int len = nums.size(); vector> res; DFS(nums,0,res); return res; } private: void DFS(vector&nums,int i,vector>& res) { if(i == nums.size())//因为每一次交换就可以将问题缩减一级，所以nums.size()次交换就可以将问题缩减为0级，0个数的全排列问题，问题最终得到解决，当然缩减到1级也是可以的（就是没有了最后自身与自身的交换而已） { res.push_back(nums); return; } for(int j = i; j < nums.size(); j++)//遍历数组，分别将每一位元素与当前数组首位元素交换 { swap(nums[i],nums[j]); //通过交换来实现全排列 DFS(nums,i+1,res); swap(nums[i],nums[j]); //进行下一次交换时，是在原数组的基础上进行的，所以必须把首位元素交换回来 } return; }};

2.给定一个数组，数组中元素可以相同，写出数组元素的全排列组合，组合中不可以出现相同的排列

例如： Input: [1,1,2,2] Output: [[1,1,2,2],[1,2,1,2],[1,2,2,1],[2,1,1,2],[2,1,2,1],[2,2,1,1]]

我们先来简单分析一下，仍然采用缩减问题的方法，遍历数组中每一个元素与第一个元素交换，得到四个数组
[1,1,2,2]; [1,1,2,2]; [2,1,1,2]; [2,1,2,1]我们发现缩减的问题有重复，有些缩减的问题是不可取的（重复），所以我们在交换之前要判断一下，该元素交换后的数组是否已经出现过，出现过则是重复问题，要舍弃；
所以在遍历元素与数组首元素交换时要判断是否已经出现过重复的结果，那么如何判断呢？
在[1,1,2,2]为一般性，我们用 i 代表数组首元素的下标，j 遍历数组元素时元素的下标，由于均与第一个元素交换，所以我们可以尝试着将第一个元素作为标志位，[1,1,2,2] i = 0,j =0时交换为[1,1,2,2]; 此时标志位为首元素1，就是说如果后面遍历的元素中再出现1，则与i=0 处的元素相交换后会产生重复（就是 i = 0,j = 1,这种情况，交换过后结果为[1,1,2,2]，重复，所以这种情况应该舍去）；当i =0,j = 2时，与标志位1不等，所以可以交换，为[2,1,1,2]，此时首元素位置处为2，标志位更新为2；这样就可以避免首元素为2的重复，(注，这里与上面不含重复元素的数组的全排列的不同之处在于，它交换后并不交换回来，而是在交换的基础上进行下去，当然这样的目的是为了避免重复)
而且这样做的前提是，数组中的元素必须按大小进行排列，否则

if(i != j && nums[i] == nums[j]) { continue; }

不能剔除掉所有的重复排列；而且由于交换后不交换回来，而且要保持遍历数组时的连续性（即这一次遍历交换在上次遍历交换的基础上进行，其实就是为了保留本次的标志位），所以程序中用的是指传递，而不是引用
这样在交换[1,1,2,2]中的第2个元素与首元素标志位后，就变为了[2,1,1,2]，之后在[2,1,1,2]的基础上进行判断，而不再采用[1,1,2,2];
【全排列问题（不含有相同元素与含有相同元素的全排列问题）】如果用引用，则由于每一次都是深度优先搜索，中间有很多次交换性，如果交换后不交换回来，则会破坏数组元素的有序性，如果交换后交换回来，则每一次又都会在[1,1,2,2]的基础上进行，而不会保留上一次的标志位
完整程序如下：

class Solution { public: vector> permuteUnique(vector& nums) { sort(nums.begin(),nums.end()); vector> res; int len = nums.size(); if(len == 0) { return res; }DFS(nums,0,res); return res; } private: void DFS(vector nums,int i ,vector> & res) { if(i == nums.size()) { res.push_back(nums); return; } for(int j = i; j < nums.size(); j++) { if(j != i && nums[i] == nums[j]) { continue; } swap(nums[i],nums[j]); DFS(nums,i+1,res); } } };

3.下一个排列
在这个问题中我们不在要求求出所以元素的全排列，而只是想知道按字典比当前排列大的最近的排列是什么，如果当前排列已经是最大排列，则给出最小排列
比如
1,2,3 → 1,3,2//1,3,2是比排列1,2,3大的最近的排列
3,2,1 → 1,2,3//3,2,1已经是最大排列，所以转写为最小排列 1,2,3
1,1,5 → 1,5,1//1,5,1 是比排列 1,1,5大的最近的排列
为简单起见先考虑整数，
比如123 ，我们想要求由这三个数字组成比它大的最近的元素我们会怎么做，由于要求比123大且差值最小，所以能不动百位数1就不动1，由于个位数3比十位数3大，所以交换后132 > 123; 符合要求
那么 1243 呢？秉承原则，高位能不动就不动，而且只能操作该位本身和低于它的位，从十位入手，由于4>3,所以不能动十位（因为4，3交换后变小），而2<4所以可以通过调整百位来使其增大，为了使其增大的最小，我们应该在4,3中选择一个比2大且差值最小的数，应选择3，同时十位和个位数应该按升序排列（由于在1243中，找到百位2时才满足高位小于低位，所以从十位到个位是降序排列的，只要对其进行反转即可），这样才能使其增大但增大的最少。
再以 56486431为例进行说明，由于 1 < 3, 3 < 4所以任意交换个十百位均只能使其减小，继续比较 4<6,6<8,8>4，所以可以调整4所在的这一位，在比4这一位低的位中进行查找大于4但差值最小的数，明显是6，与之交换，变为 56 684431，我们发现交换完毕后，6之后的数明显是降序排列，所以我们对其进行翻转就可以得到我们的目标数，56 613448，这就是比56486431大但差值最小的数，也是这几个数的全排列
完整程序如下：需要先进行相邻位的比较，找到需要调整的位，然后在比该位低的位中找一个比该位处的数大但差值最小的数，交换两者，然后将该位之后的元素进行翻转

class Solution { public: void nextPermutation(vector& nums) { //寻找应该被交换的点 int i = nums.size()-2; while(i >= 0 && nums[i+1] <= nums[i])//找到需要调整的位。如果该数组元素排列已经是最大值，则 i = -1; 最后将数组全部翻转即可 { i--; } if(i >= 0) { int j = nums.size()-1; while(i >= 0 && nums[j] <= nums[i])//找到比需要调整位处的数大但查找最小的数 { j--; } swap(nums[i],nums[j]); //交换两者} reverse(nums.begin()+i+1,nums.end()); //翻转 } };