-
全排列问题(不含有相同元素与含有相同元素的全排列问题)
2019-07-23 22:20:161.给定一个数组,数组中元素均不相同,写出数组元素的全排列组合 比如: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 由于数组中不含相同元素,所有不用考虑重复问题,...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,3 2,1,3 3,2,1 //遍历数组将数组元素分别与第一位元素交换,缩减问题为两个数的全排列问题,将问题缩减为了[2,3];[1,3];[2,1]的全排列问题 / \ / \ / \ 1,2,3 1,3,2 2,1,3 2,3,1 3,2,1 3,1,2 //遍历数组[2,3],将数组元素分别与第一位元素交换,将问题缩减为1个数的全排列问题,即将问题缩减为[2]和[3]的全排列问题;其他数组[1,3];[2,1]类似处理 | | | | | | 1,2,3 1,3,2 2,1,3 2,3,1 3,2,1 3,1,2 //可以继续这一步,也可以不继续,就是i = nums.size() 和nums.size()-1的区别 所以明显看出可以用深度优先搜索解决,因为每一步所做的处理是相同的
class Solution { public: vector<vector<int>> permute(vector<int>& nums) { int len = nums.size(); vector<vector<int>> res; DFS(nums,0,res); return res; } private: void DFS(vector<int>&nums,int i,vector<vector<int>>& 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<vector<int>> permuteUnique(vector<int>& nums) { sort(nums.begin(),nums.end()); vector<vector<int>> res; int len = nums.size(); if(len == 0) { return res; } DFS(nums,0,res); return res; } private: void DFS(vector<int> nums,int i ,vector<vector<int>> & 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<int>& 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());//翻转 } };
-
含有重复字符的全排列问题以及按字典序打印
2017-09-24 17:55:37给定一字符串,可能含有相同元素。请借助递归设计算法求出该字符串的所有不同的排序。输入格式:第一行输入一个整数T(小于等于10),代表有T组测试样例。接下来T行,每行给定一串字符串(长度小于等于9,且至少有3个...关于字符的全排列问题也是有很多算法的,今天我就来介绍递归的Perm算法。直接看题吧。。。
给定一字符串,可能含有相同元素。请借助递归设计算法求出该字符串的所有不同的排序。
输入格式:
给定一串字符串(长度小于等于9,且至少有3个字符相同)。
输出格式:
每行输出一个字符串。按照字典序递增的顺序输出,每个排列占一行。
最后一行输出不同排列的个数。
题目大体意思就是要我们求一个字符串的全排列,说到递归,那么Perm算法出来了,Perm算法核心思想是把m个待排元素每一个依次拿到首位,剩下的m-1个组成新的待排元素传入Perm进行相同的操作……….以此类推,直到元素递归到只有一个了,就依次打印出来 形成一个排列
先上算法的核心部分:
void Perm(char b[],int low,int high,int& n)//这里把待排序元素放入char型数组b中,待排元素起始下 //标为low,末尾下标为high,n用来计有多少种不同的排列组合 { if(low == high) //如果递归排到只有最后一个元素,就按序打印出来 { for(int i = 0;i < low;i++) { printf("%c",b[i]); } n++; //打印一次计数值加1 printf("\n"); //每打印一次排列就换一次行 } else //如果传进来的待排字符不止一个字符 { for(int i = low;i < high;i++) { swap(b[low],b[i]); //把每个元素挨个拿到首部low的位置 Perm(b,low+1,high,n); //除拿到首部之外剩下的再进入Perm递归 swap(b[low],b[i]); //还原字符串为交换前的样子,以进行下个字符的交换 } } }
这只是Perm最原始思想的体现,目前还不具备处理重复元素的能力,比如aabc,把第一个a拿到首位和把第二个a拿到首位,再让其与字符进行全排列后的效果是一样的,因此,我们在交换前应该加一个判断,如果在该字符位置之前存在相同的字符,该字符就不进行多余的交换了,跳往下一个字符的判断,修改代码如下:
for(int i = low;i < high;i++) { if(isSwap(b,low,i)) //交换前判断之前是否有相同的元素被拿到首位过 { swap(b[low],b[i]); Perm(b,low+1,high,n); swap(b[low],b[i]); } }
当然了,到目前位置还存在的一个问题就是没有满足字典序打印的问题,由于该算法是一个元素一个元素输出的,所以没有办法在得到结果之后在进行排序,只得对算法本身加以调整,如下:
for(int i = low;i < high;i++) { sort(b+low,b+high);//把每次递归传进来的元素先排个序,用了sort库函数,它包含在在头文件<algorithm>中 if(isSwap(b,low,i)) { swap(b[low],b[i]); Perm(b,low+1,high,n); swap(b[low],b[i]); } }
这样工作就都做完啦。。
这一题完整代码如下:
#include<iostream> #include<algorithm> using namespace std; void swap(char& a,char& b) //两个元素进行交换 { char c = a; a = b; b = c; } bool isSwap(char b[], int start, int i) //i为该元素下标 { for(int k = start; k<i;k++) //判断在该元素之前有没有相同元素 if(b[k] == b[i]) return false; //如果有,则返回false return true; } void Perm(char b[],int low,int high,int& n) //核心的算法啦 { if(low == high) { for(int i = 0;i < low;i++) { printf("%c",b[i]); } n++; printf("\n"); } else { for(int i = low;i < high;i++) { sort(b+low,b+high); if(isSwap(b,low,i)) { swap(b[low],b[i]); Perm(b,low+1,high,n); swap(b[low],b[i]); } } } } int main() { int n = 0; //计数用的 string str; cin>>str; //用字符串接收待排元素 char b[9] ; int i = 0; while(str[i]!='\0') { b[i] = str[i]; //把待排元素装进字符数组中 i++; } Perm(b,0,str.length(),n); //调用Perm进行排序 cout<<n<<endl; //输出总排列个数 }
-
如何得到有重复元素的不重复全排列
2012-03-23 16:42:50M个元素中含有相同的元素,如何得到他们的全排列(不重复排列)? 元素表述: a1,a1,...a1, a2,a2,...a2,.......,an,an,...an 其中,a1的个数为N1, a2的个数为N2,以此类推,总个数为M。 则可以证明不...M个元素中含有相同的元素,如何得到他们的全排列(不重复排列)?
元素表述: a1,a1,...a1, a2,a2,...a2,.......,an,an,...an
其中,a1的个数为N1, a2的个数为N2,以此类推,总个数为M。
则可以证明不重复的排列种类的数目: M!/(N1!*N2!*...*Nn!)就是将N个数字做全排列。不过对于某些数字不能选择而已。
这里只要限制将要选择的数字必须大于原来已经选择的数字就可以达到目标。
下面是递归算法#include <stdio.h> #define N 5 void arrange(int rec[],int used[],int depth); void write(int rec[], int maxdepth); int a[N]={1,1,2,2,3}; //这些值必须升序排列且大于0 int count=0; int main() {int rec[N+1]={0},used[N+1]={0}; arrange(rec,used,0); printf( "\ncount=%d ",count); getchar(); return 0; } void write(int rec[]) { int i; for(i=0;i <N;i++) printf( "%4d ",a[rec[i]]); printf( "\n "); count++; } void arrange(int rec[],int used[],int depth) { int i,found_num; if (depth> =N) write(rec); //找到了一个可行解,输出 else {found_num=0; //增加这个变量记录原来本结点存储的数字 for(i=0;i <N;i++) // 搜索该结点的孩子结点 {//如果该下标在前面还没有使用过,且该下标所指示的数字比 //原先所放置的数字要大,则是一个部分解 if(used[i]==0 && a[i]> found_num ) { rec[depth]=i; //记录下该结点放置的下标 found_num=a[i]; //记录下本结点存放的数字 used[i]=1; // 标记该下标已经被使用 arrange(rec,used,depth+1); // 扩展,进入孩子结点继续搜索 used[i]=0; //退回来后要清除本结点所记录下标的使用记录 } } } }
-
全排列问题
2019-04-30 17:16:18含有重复数字的全排列问题 算法1 (回溯算法) O(n2)O(n^2)O(n2) 由于有重复元素的存在,这道题的枚举顺序和 Permutations 不同。 先将所有数从小到大排序,这样相同的数会排在一起; 从左到右依次枚举每个数,每次将...全排列问题
含有重复数字的全排列问题
算法1
(回溯算法)
由于有重复元素的存在,这道题的枚举顺序和 Permutations 不同。
- 先将所有数从小到大排序,这样相同的数会排在一起;
- 从左到右依次枚举每个数,每次将它放在一个空位上;
- 对于相同数,我们人为定序,就可以避免重复计算:我们在dfs时记录一个额外的状态,记录上一个相同数存放的位置 start,我们在枚举当前数时,只枚举 start+1,start+2,…,nstart+1,start+2,…,n 这些位置。
- 不要忘记递归前和回溯时,对状态进行更新。
时间复杂度分析:搜索树中最后一层共 n! 个节点,前面所有层加一块的节点数量相比于最后一层节点数是无穷小量,可以忽略。且最后一层节点记录方案的计算量是,所以总时间复杂度是 。
C++ 代码
class Solution { public: vector<bool> st; vector<int> path; vector<vector<int>> ans; vector<vector<int>> permutation(vector<int>& nums) { sort(nums.begin(), nums.end()); st = vector<bool>(nums.size(), false); path = vector<int>(nums.size()); dfs(nums, 0, 0); return ans; } void dfs(vector<int>& nums, int u, int start) { if (u == nums.size()) { ans.push_back(path); return; } for (int i = start; i < nums.size(); i ++ ) if (!st[i]) { st[i] = true; path[i] = nums[u]; if (u + 1 < nums.size() && nums[u + 1] != nums[u]) dfs(nums, u + 1, 0); else dfs(nums, u + 1, i + 1); st[i] = false; } } };
互不相同数字的全排列问题
算法1
(回溯算法)
我们从前往后,一位一位枚举,每次选择一个没有被使用过的数。
选好之后,将该数的状态改成“已被使用”,同时将该数记录在相应位置上,然后递归。
递归返回时,不要忘记将该数的状态改成“未被使用”,并将该数从相应位置上删除。时间复杂度分析:搜索树中最后一层共 n! 个节点,前面所有层加一块的节点数量相比于最后一层节点数是无穷小量,可以忽略。且最后一层节点记录方案的计算量是,所以总时间复杂度是 。
C++ 代码
class Solution { public: vector<vector<int>> ans; vector<bool> st; vector<int> path; vector<vector<int>> permute(vector<int>& nums) { for (int i = 0; i < nums.size(); i ++ ) st.push_back(false); dfs(nums, 0); return ans; } void dfs(vector<int> &nums, int u) { if (u == nums.size()) { ans.push_back(path); return ; } for (int i = 0; i < nums.size(); i ++ ) if (!st[i]) { st[i] = true; path.push_back(nums[u]); dfs(nums, u + 1); st[i] = false; path.pop_back(); } } };
当然也可以用stl库里面的函数next_permutation函数
class Solution { public: vector<vector<int>>ans; vector<vector<int>> permuteUnique(vector<int>& nums) { sort(nums.begin(),nums.end()); do { ans.push_back(nums); } while (next_permutation(nums.begin(), nums.end())); return ans; } };
参考
-
怎么获取数组的全排列
2015-11-23 00:59:05在这m个List中各取一元素组合成一个新的含有m个元素的List,所有可能组合就有k1*k2*...*km种,现在要求将这些组合列出来。 正常的话m个循环嵌套就可以写出来,但现在m相当于也是输入参数了,事先并不知道m是多少,... -
【计蒜客】全排列 去重
2018-03-11 20:47:52全排列 相信大家都知道什么是全排列,但是今天的全排列比你想象中的难一点。我们要找的是全排列中,排列结果互不...【分析】含有重复元素的全排列问题 关键:去重【答案】vis[j] && str[i]==st... -
全排列II
2020-03-05 23:05:34大体框架还是和上一道题类似,只是需要多一个去重的条件,那么我们可以发现,如果某个节点的取值的上一个是未使用的,并且该节点的关键字和上一个元素的关键字相同,那么就说明存在相同的分支,则需要将其剪掉(按照... -
利用递归输出全排列
2016-09-12 21:47:13举个例子,现在我们有一个含有1,2,3三个元素的数组,现在我们准备找出它们的全排列。大部人的做法是先在第一个位置放1,第二个位置放2,第三个地方放3;然后还是第一个位置放1,交换2和3的位置;之后换成2放在第一... -
回溯算法
2020-08-09 19:49:57回溯算法回溯算法深度优先算法(DFS)剪枝求解八皇后问题(java代码)问题描述求解思想代码实现求解数组元素全排列问题(java代码)问题描述求解思想代码实现用剪枝来求解含有相同元素的全排列问题 回溯算法 回溯算法... -
LeetCode Permutations II (全排列)
2015-11-03 16:09:00给出n个元素(可能有重复的),请产生出所有的全排列。 思路: 同版本1的有点不同,这次有可能含有重复的元素,很容易就TLE,节省时间才是关键点。 如果将一个序列中两个相同的元素交换,这个序列是仍然... -
排列组合相关笔试面试题(C++)
2016-04-12 10:23:24含有相同元素的全排列:例如2个a,3个b,4个c可以组成多少个不同的字符串?9!/2!/3!/4!。 n个人的全排列:排成一排为n!,排成一圈且考虑旋转带来的差异也为n!,排成一圈但不考虑旋转差异则为(n-1)!。 二、普通排列... -
#418 Div2 Problem B An express train to reveries (构造 || 全排列序列特性)
2019-09-30 04:09:52题意 : 有一个给出两个含有 n 个数的序列 a 和 b, 这两个序列和(1~n)的其中一个全排列序列 p 只有一个元素不同, 要求你找出任意满足这个条件的序列 p 分析 : 全排列有个特点, 就是各个元素各不相同, 只要改变了... -
leetcode经典排列问题
2020-07-25 10:38:52文章目录推荐题目Permutations字典序法——nextPermutation版本一版本二不含重复元素的全排列含有重复元素的全排列Kth Permutation 推荐题目 LeetCode 上有几道题都和排列组合有关,非常经典,值得放在一起总结一下... -
算法实践学习笔记2
2020-10-12 23:41:13重点:在不含重复字符的全排列的基础上想办法使得在树的同一层不会添加相同的元素 解决方法:在找全排列序列之前将原序列按字典的顺序进行排序,然后再找全排列序列。 注意: 每一层构造完之后要重新排序恢复... -
组合数C(n,m)的计算
2015-09-03 18:25:23n个互不相同的数的全排列是n!个。 一个有n个元素的集合的含有m个元素子集的个数为C(n,m)。 C(n,m)的计算方式: 1.公式:C(n,m) = n!/((n-m)! * m!),在算法上较难实现,阶乘很快会爆long long 2.递推:C(n,m) = C(n... -
【丙】搜索,回溯
2020-09-11 20:37:30文章目录BFS1. 计算在网格中从原点到特定点的最短路径长度2. 组成整数的最小平方数数量3. 最短单词路径DFS1. 查找最大的连通面积2. 矩阵中的连通分量数目(岛屿数量)2.1 岛屿... 含有相同元素求排列第k个排列7. 组合8. -
C#编程经验技巧宝典
2008-06-01 08:59:3354 <br>0075 用回溯法找出n个自然数中取r个数的全排列 55 <br>0076 约瑟夫环问题 56 <br>0077 猴子选大王 57 <br>0078 如何判断IP是否正确 57 <br>0079 如何将小写金额转换为大写金额 57...
-
视频监控系统中的大数据问题调查
-
vue3 骨架屏+上拉加载更多封装
-
JS_H5禁止手机自带键盘弹出
-
解除B站区域限制.user.js
-
MySQL 数据库的基本操作(数据完整性约束)
-
Astyle-source insight 安装及使用方法.zip
-
代理服务器的ip从哪里找?
-
华为1+X——网络系统建设与运维(中级)
-
相机简介以及用途汇总.docx
-
postwoman.v.1.1.7.zip
-
java 获取字符串最后的数字
-
C#Winform桌面开发编程上位机基础入门
-
短波Moxon 定向天线计算软件.zip
-
北京浮生记:20年前国产个人小游戏.zip
-
C语言:猴子吃桃问题。
-
生物医药:创新药周报20210228.pdf
-
【宝物志】门店运营内容分享 第二十期
-
U盘 固态检测软件.rar
-
2021年 系统架构设计师 系列课
-
html打开的协议是https 协议不是 file 协议