北京网站建设兼职,虚拟主机销售网站,国内人做韩国网站一般都卖什么手续,wordpress主题 路径接触全排列已经好长时间了#xff0c;一直没有抽空总结一下全排列的相关问题#xff0c;下面来说一下#xff01; 排列 一般地#xff0c;从n个不同元素中取出m#xff08;m≤n#xff09;个元素#xff0c;按照一定的顺序排成一列#xff0c;叫做从n个元素中取出m个元… 接触全排列已经好长时间了一直没有抽空总结一下全排列的相关问题下面来说一下 排列 一般地从n个不同元素中取出mm≤n个元素按照一定的顺序排成一列叫做从n个元素中取出m个元素的一个排列(Arrangement)。特别地当mn时这个排列被称作全排列(Permutation)。 排列数公式 特别当nm时为全排列的公式 下一个全排列算法 lintcode链接http://www.lintcode.com/zh-cn/problem/next-permutation/ 样例 左边是原始排列右边是对应的下一个排列。 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1 下一个全排列算法——first class Solution {
public:/*** param nums: a vector of integers* return: return nothing (void), do not return anything, modify nums in-place instead*/void nextPermutation(vectorint nums) {//调用algorithm中的下一个排列算法以及排序算法if(!next_permutation(nums.begin(), nums.end()))sort(nums.begin(), nums.end(), lessint()); }} 下一个全排列算法——second class Solution {
public:/*** param nums: a vector of integers* return: return nothing (void), do not return anything, modify nums in-place instead*/void nextPermutation(vectorint nums) {int ld -1;if(nums.size() 1) return ;for(int inums.size()-2; i0; --i)//找到从右边开始第一个比它右边相邻小的数的位置if(nums[i] nums[i1]){ld i;break;}if(ld ! -1){//找到从右边开始第一个比位置为ld所在数 大的数的位置int rd;for(int inums.size()-1; i0; --i)if(nums[ld] nums[i]){rd i;break;}swap(nums[ld], nums[rd]);//在交换之前ld位置后面的已经是从大到小排好序的已经没有下一个排列了sort(nums.begin()ld1, nums.end());//交换之后将ld后面的数置为最小的排列从小到大排序}if(ld -1){sort(nums.begin(), nums.end());}}
}; 下一个全排列算法——third class Solution {
public:/*** param nums: a vector of integers* return: return nothing (void), do not return anything, modify nums in-place instead*/void nextPermutation(vectorint nums) { //挑战不使用额外的空间, 其实和方法二的思路是一样的int n nums.size();for(int in-1; i0; --i)for(int jn-1; ji; --j)if(nums[i] nums[j]){swap(nums[i], nums[j]);sort(nums.begin()i1, nums.end());return ;}sort(nums.begin(), nums.end());}
}; 下一个全排列的思想 如上图所示该全排列对应的下一个全排列是和绿色框里的数字以及红色框里的数字有关系的。显而易见的是红色框里的数列已经没有下一个排列了因为已经是一个递减的序列了。为了得到下一个排列我们将绿色框里的数字和红色框里右边起第一个比绿色框中数字大的数字交换位置(也就是4 和 5交换位置)。这样还不是下一个全排列交换之后红色框内的序列为7 4 3 2 1 0 将它变成递增序列 0 1 2 3 4 7就得到了下一个全排列。 因为一个全排列末尾的一段区间肯定是递减的如上图的红色框区间如果这段区间一直延伸到首部那么也就没有下一个全排列了否则找到和这段区间最近的一个数字上图中绿色框中的数字然后经过上述的处理就可以得到下一个全排列了。 the second method 就是先找到绿色框数字的位置(ld) 然后在寻找红色框中右边第一个比绿色框中数字大的数字的位置(rd); the third method的意思就是从右边开始寻找第一对(i, j)满足nums[i]nums[j], 对应second method中(ld, rd)。该方法没有用到额外的存储空间。 上一个全排列算法 注算法思想和下一个全排列的思想正好相反步骤一致 lintcode链接:http://www.lintcode.com/zh-cn/problem/previous-permutation/ 样例 给出排列[1,3,2,3]其上一个排列是[1,2,3,3] 给出排列[1,2,3,4]其上一个排列是[4,3,2,1] 上一个全排列算法——first class Solution {
public:/*** param nums: An array of integers* return: An array of integers thats previous permuation*/vectorint previousPermuation(vectorint nums) { //直接调用algrotihm中的算法prev_permutation()if(!prev_permutation(nums.begin(), nums.end()))sort(nums.begin(), nums.end(), greaterint());return nums; }
}; 上一个全排列算法——second class Solution {
public:/*** param nums: An array of integers* return: An array of integers thats previous permuation*/vectorint previousPermuation(vectorint nums) { int ld -1;if(nums.size() 1) return nums;for(int inums.size()-2; i0; --i)//找到从右边开始第一个比它右边相邻大的数的位置if(nums[i] nums[i1]){ld i;break;}if(ld ! -1){//找到从右边开始第一个比位置为ld所在数 小的数的位置int rd;for(int inums.size()-1; i0; --i)if(nums[ld] nums[i]){rd i;break;}swap(nums[ld], nums[rd]);//在交换之前ld位置后面的已经是从小到大排好序的已经没有上一个排列了//交换之后将ld后面的数置为最大的排列从大到小排序sort(nums.begin()ld1, nums.end(), greaterint());}if(ld -1){sort(nums.begin(), nums.end(), greaterint());}return nums; }
}; 上一个全排列算法——third class Solution {
public:/*** param nums: An array of integers* return: An array of integers thats previous permuation*/vectorint previousPermuation(vectorint nums) { int n nums.size();for(int in-1; i0; --i)for(int jn-1; ji; --j)if(nums[i] nums[j]){swap(nums[i], nums[j]);sort(nums.begin()i1, nums.end(), greaterint());return nums;}sort(nums.begin(), nums.end(), greaterint());return nums;}
}; 得到所有全排列算法 lintcode链接http://www.lintcode.com/zh-cn/problem/permutations/ 全排列算法——first 注非递归由下一个全排列算法——third方法实现 class Solution {
public:/*** param nums: A list of integers.* return: A list of permutations.*/vectorvectorint vv;vectorvectorint permute(vectorint nums) {if(nums.size() 0) return vv;sort(nums.begin(), nums.end());//方法1 非递归实现int n nums.size();bool flag true;vv.push_back(nums);while(flag){flag false;for(int in-1; i0; --i){for(int jn-1; ji; --j)if(nums[i] nums[j]){swap(nums[i], nums[j]);sort(nums.begin()i1, nums.end());vv.push_back(nums);flag true;break;}if(flag) break;}} return vv;}
}; 全排列算法——second class Solution {
public:/*** param nums: A list of integers.* return: A list of permutations.*/vectorvectorint vv;vectorvectorint permute(vectorint nums) {if(nums.size() 0) return vv;sort(nums.begin(), nums.end()); //方法2调用algorithm中的next_permutation()do{vv.push_back(nums);}while(next_permutation(nums.begin(), nums.end())); return vv;}
}; 全排列算法——third 注递归思路一共有nn个位置然后每个位置枚举可能出现的数字注意处理重复数字的情况 class Solution {
public:/*** param nums: A list of integers.* return: A list of permutations.*/vectorvectorint vv; ///int nn;//没有 unique 之前的数组的大小mapint, int mp; void dfs_1(int cur, vectorint v, vectorint nums){if(cur nn){vv.push_back(v);return;}for(int i0; inums.size(); i)if(mp[nums[i]]){//如果nums[i]这个数字没有枚举完--mp[nums[i]];v.push_back(nums[i]);dfs_1(cur1, v, nums);v.pop_back();mp[nums[i]];}} //// vectorvectorint permute(vectorint nums) {if(nums.size() 0) return vv;sort(nums.begin(), nums.end()); //方法3递归for(int i0; inums.size(); i)//统计每个重复元素的个数mp[nums[i]];nn nums.size();unique(nums.begin(), nums.end());//对数组进行去重vectorint v;dfs_1(0, v, nums); return vv;}
}; 全排列算法——forth 注递归思路每一个数不断的和后面的数交换位置每交换一次就会得到一个新的排列 class Solution {
public:/*** param nums: A list of integers.* return: A list of permutations.*/vectorvectorint vv;void dfs_2(int ld, int rd, vectorint nums){if(ld rd){vv.push_back(nums);return ;}for(int ild; ird; i){swap(nums[ld], nums[i]);dfs_2(ld1, rd, nums);swap(nums[ld], nums[i]);}}vectorvectorint permute(vectorint nums) {if(nums.size() 0) return vv;sort(nums.begin(), nums.end()); dfs_2(0, nums.size()-1, nums);return vv;}
}; 排列序号(按字典序排序属于第几个全排列) 注不含重复数字的排列 lintcode链接http://www.lintcode.com/zh-cn/problem/permutation-index/ 样例 例如排列[1,4,2]是第2个全排列。 排列序号算法 算法思想请参考http://www.cnblogs.com/hujunzheng/p/5020211.html class Solution {
public:/*** param A an integer array* return a long integer*/long long permutationIndex(vectorint A) {//一个一个来肯定会超时// vectorint permu(A.begin(), A.end());// sort(permu.begin(), permu.end());// int cnt 0;// do{// int i;// for(i0; iA.size(); i)// if(A[i]!permu[i])// break;// cnt;// if(iA.size()) break;// }while(next_permutation(permu.begin(), permu.end()));// return cnt;vectorint a;int len A.size();int cnt[len];cnt[len-1] 0;a.push_back(A[len-1]);for(int ilen-2; i0; --i){//统计每个数后面有多少个比它小的数的个数vectorint::iterator it lower_bound(a.begin(), a.end(), A[i]);cnt[i] it-a.begin();a.insert(it, A[i]);}long long ans1, fac1, c1;for(int ilen-2; i0; --i)ans (fac*c)*cnt[i];return ans;}
}; 第k个排列 注给定 n 和 k求123..n组成的排列中的第 k 个排列。 lintcode链接http://www.lintcode.com/zh-cn/problem/permutation-sequence/ 样例 对于 n 3, 所有的排列是123, 132, 213, 231, 312, 321. 如果 k 4, 第4个排列为231. 康托展开的公式 Xan*(n-1)!an-1*(n-2)!...ai*(i-1)!...a2*1!a1*0!ai为整数并且0aii(1in) 适用范围没有重复元素的全排列 例题 找出第16个n 5的序列12345。康托展开只要O(n)就行 下面来说说具体怎么做: 根据第一行的那个全排列公式15 / 4! 0 …15 有0个数比它小的数是1所以第一位是1 拿走刚才的余数15用15 / 3! 2 …3 剩下的数里有两个数比它小的是41已经没了所以第二位是4 拿走余数3 用 3 / 2! 1 …1 剩下的数里有一个数比它小的是3所以第三位是3 拿走余数1 用 1/ 1! 1 …0 剩下的数里有一个数比它小的是 5只剩2和5了所以第四位是5 所以排列是 1,4,3,5,2 第k个排列算法 class Solution {
public:/*** param n: n* param k: the kth permutation* return: return the k-th permutation*/string getPermutation(int n, int k) {if(n1) return 1;int f[n1];bool use[n1];f[1] 0;f[2] 1;memset(use, false, sizeof(use));for(int i3; in; i)f[i] f[i-1]*(i-1);string ans ;--k;//要计算的排列之前有多少个排列for(int in; i2; --i){int cnt 0;int c k/f[i];//假设该排列的这位数是xc就是比x小的数之前没有用过的个数k%f[i];for(int j1; jn; j){//寻找符合要求的x的值if(!use[j]){if(cnt c){ans j0;use[j] true;break;}cnt;}}}for(int j1; jn; j)if(!use[j]){ans j0;break;}return ans;}
}; 带重复元素的排列 题目链接http://www.lintcode.com/zh-cn/problem/permutations-ii/ 带重复元素的排列——first 思路next_permutation()本身支持带重复元素的全排列 class Solution {
public:/*** param nums: A list of integers.* return: A list of unique permutations.*/vectorvectorint ans;vectorvectorint permuteUnique(vectorint nums) {// write your code heresort(nums.begin(), nums.end());do{ans.push_back(nums);}while(next_permutation(nums.begin(), nums.end()));return ans;}
}; 带重复元素的排列——second 思路枚举每个位置肯能出现的数字。 class Solution {
public:/*** param nums: A list of integers.* return: A list of unique permutations.*/vectorvectorint ans;mapint, int cnt;//记录每个数字在nums中出现的次数 void dfs(int n, vectorint nums, vectorint v){if(v.size() n){ans.push_back(v);return ;}for(int i0; inums.size(); i)if(cnt[nums[i]]){--cnt[nums[i]];v.push_back(nums[i]);dfs(n, nums, v);v.pop_back();cnt[nums[i]];}}vectorvectorint permuteUnique(vectorint nums) {// write your code heresort(nums.begin(), nums.end());for(int i0; inums.size(); i)cnt[nums[i]];int n nums.size();nums.erase(unique(nums.begin(), nums.end()), nums.end());//清除重复的元素vectorint v;dfs(n, nums, v);return ans;}
}; 带重复元素的排列——third 思路和 “全排列算法——first”方法类似唯一不同的是下面代码中红色部分。 class Solution {
public:/*** param nums: A list of integers.* return: A list of unique permutations.*/vectorvectorint ans;vectorvectorint permuteUnique(vectorint nums) {// write your code heresort(nums.begin(), nums.end()); bool flag true;while(flag){flag false;ans.push_back(nums);for(int inums.size()-1; i0; --i){for(int jnums.size()-1; ji; --j)if(nums[i] nums[j]){flag true;while(j-1i nums[j-1]nums[j]) --j;//如果前面有相同的数字找到最左边的数字swap(nums[i], nums[j]);sort(nums.begin()i1, nums.end());break;}if(flag) break;}}return ans;}
}; 转载于:https://www.cnblogs.com/hujunzheng/p/5037121.html
