电商网站 设计,专业的网页设计和网站建设公司,wordpress4.2下载,免费下载百度一下全排列的简要总结
全排列#xff08;Permutation#xff09;是数学中一个经典的问题#xff0c;指的是从一组元素中#xff0c;将所有元素按任意顺序排列形成的所有可能序列。 特点 输入条件#xff1a; 给定一组互异的元素#xff08;通常为数组或字符串#xff09;。…全排列的简要总结
全排列Permutation是数学中一个经典的问题指的是从一组元素中将所有元素按任意顺序排列形成的所有可能序列。 特点 输入条件 给定一组互异的元素通常为数组或字符串。例如[1, 2, 3] 的全排列。 输出结果 输出所有元素的排列组合。例如[1, 2, 3] 的全排列是[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]数量公式 对于 n 个互异元素其全排列数量为 n ! n! n!阶乘。例如n 3 时全排列数量为 3 ! 6 3! 6 3!6。 实现方式
1. 递归法
通过递归交换或回溯实现
#include iostream
#include vector
using namespace std;void backtrack(vectorint nums, int start, vectorvectorint result) {if (start nums.size()) {result.push_back(nums);return;}for (int i start; i nums.size(); i) {swap(nums[start], nums[i]); // 交换当前元素backtrack(nums, start 1, result); // 递归处理子问题swap(nums[start], nums[i]); // 撤销交换回溯}
}int main() {vectorint nums {1, 2, 3};vectorvectorint result;backtrack(nums, 0, result);for (const auto perm : result) {for (int num : perm) {cout num ;}cout endl;}return 0;
}2. STL 函数
C 提供了 std::next_permutation可以简单地生成字典序全排列
#include iostream
#include vector
#include algorithm
using namespace std;int main() {vectorint nums {1, 2, 3};do {for (int num : nums) {cout num ;}cout endl;} while (next_permutation(nums.begin(), nums.end())); // 调用 STL 函数return 0;
}应用场景 组合数学 求解排列问题、旅行商问题等。 字符串操作 对字符串生成不同排列用于密码学、模式匹配等。 游戏与搜索 如数独解法、八皇后问题等依赖全排列进行搜索。 算法优化 通过排列测试不同的输入顺序寻找最优解。 优化与注意事项 剪枝优化 在递归中排除不合法或重复的排列提高效率。 重复元素 如果输入包含重复元素需要特殊处理以避免重复结果。 大规模问题 对于规模较大的输入因 n ! n! n! 增长较快可能需要改用启发式算法。
全排列是基础的数学与算法问题其思想在递归、动态规划和搜索算法中广泛应用
1.全排列
题目链接全排列 题目概述 解题思路递归流程如下
⾸先定义⼀个⼆维数组res⽤来存放所有可能的排列⼀个⼀维数组ans⽤来存放每个状态的排 列⼀个⼀维数组visited标记元素然后从第⼀个位置开始进⾏递归在每个递归的状态中我们维护⼀个步数step表⽰当前已经处理了⼏个数字递归结束条件当step等于nums数组的⻓度时说明我们已经处理完了所有数字将当前数组 存⼊结果中在每个递归状态中枚举所有下标i若这个下标未被标记则使⽤nums数组中当前下标的元 素 a. 将visited[i]标记为1 b. ans数组中第step个元素被nums[i]覆盖 c. 对第step1个位置进⾏递归 d. 将visited[i]重新赋值为0表⽰回溯最后返回res。 • 特别地我们可以不使⽤标记数组直接遍历step之后的元素未被使⽤然后将其与需要递 归的位置进⾏交换即可。
class Solution {vectorvectorint it;vectorint path;bool check[7];//check用来存储是否被使用过public:void dfs(vectorint nums, vectorint path) {if (path.size() nums.size()) {it.push_back(path);}else {for (int a 0; a nums.size(); a) {if (!check[a]) {path.push_back(nums[a]);check[a] true;//标记下次不能再选dfs(nums, path);check[a] false;//回溯复原path.pop_back();}}}}vectorvectorint permute(vectorint nums) {dfs(nums, path);return it;}
};2.子集
题目链接子集 题目介绍 解题思路
递归结束条件如果当前需要处理的元素下标越界则记录当前状态并直接返回在递归过程中对于每个元素我们有两种选择 ◦ 不选择当前元素直接递归到下⼀个元素 ◦ 选择当前元素将其添加到数组末尾后递归到下⼀个元素然后在递归结束时撤回添加操作所有符合条件的状态都被记录下来返回即可。
class Solution {
public:vectorvectorint ret;vectorint path;void dfs(vectorint nums, int pos) {if (pos nums.size()) {ret.push_back(path);return;}// 选path.push_back(nums[pos]);dfs(nums, pos 1);path.pop_back(); // 恢复现场// 不选dfs(nums, pos 1);}vectorvectorint subsets(vectorint nums) {dfs(nums, 0);return ret;}
};3.全排列||
题目链接全排列 题目介绍 解题思路 因此我们需 要对相同元素定义⼀种规则使得其组成的排列不会形成重复的情况
我们可以将相同的元素按照排序后的下标顺序出现在排列中通俗来讲若元素s出现x次则排序后的第2个元素s⼀定出现在第1个元素s后⾯排序后的第3个元素s⼀定出现在第2个元素s后⾯以此类推此时的全排列⼀定不会出现重复结果。例如a11a21a32排列结果为[1,1,2]的情况只有⼀次即a1在a2前⾯因为a2不会出现在a1前⾯从⽽避免了重复排列。我们在每⼀个位置上考虑所有的可能情况并且不出现重复注意若当前元素的前⼀个相同元素未出现在当前状态中则当前元素也不能直接放⼊当前状态的数组此做法可以保证相同元素的排列顺序与排序后的相同元素的顺序相同即避免了重复排列出现。通过深度优先搜索的⽅式不断地枚举每个数在当前位置的可能性并在递归结束时回溯到上⼀个状态直到枚举完所有可能性得到正确的结果。
class Solution {vectorint path;vectorvectorint ret;bool check[9];public:vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(), nums.end());//先进行排序dfs(nums);return ret;}void dfs(vectorint nums) {if (path.size() nums.size()) {ret.push_back(path);return;}for (int i 0; i nums.size(); i) {// 剪枝if (check[i] false (i 0 || nums[i] ! nums[i - 1] || check[i - 1] ! false))//非常的巧妙想要插入必须满足以下要求 1.没有被插入过 2.第一位没有前一项||当前项和其前一项不一样||前一项已经被插入过了{path.push_back(nums[i]);check[i] true;dfs(nums);path.pop_back(); // 恢复现场check[i] false;}}}
};4.括号生成
题目链接括号生成 题目介绍
解题思路 从左往右进⾏递归在每个位置判断放置左右括号的可能性若此时放置左括号合理则放置左括号 继续进⾏递归右括号同理。 ⼀种判断括号是否合法的⽅法从左往右遍历左括号的数量始终⼤于等于右括号的数量并且左括 号的总数量与右括号的总数量相等。因此我们在递归时需要进⾏以下判断
放⼊左括号时需判断此时左括号数量是否⼩于字符串总⻓度的⼀半若左括号的数量⼤于等于字符 串⻓度的⼀半时继续放置左括号则左括号的总数量⼀定⼤于右括号的总数量放⼊右括号时需判断此时右括号数量是否⼩于左括号数量。
class Solution {
public:vectorstring str;void dfs(string it, int left,int right){if(left0)//做括号全部用完{while(right){it.push_back());right--;}str.push_back(it);return;}it.push_back(();//插入左括号dfs(it,left-1,right);it.pop_back();//回溯回复现场if(rightleft)//右括号剩余必须比左括号多{it.push_back());dfs(it,left,right-1);it.pop_back();//回溯}}vectorstring generateParenthesis(int n) {string it;int leftn;int rightn;it.push_back(();//左边先插入一个避免第一个就是的错误left--;dfs(it,left,right);return str;}
};5.组合
题目链接组合 题目介绍 题⽬要求我们从1到n中选择k个数的所有组合其中不考虑顺序。也就是说[1,2]和[2,1]等价。我 们需要找出所有的组合但不能重复计算相同元素的不同顺序的组合。对于选择组合我们需要进⾏ 如下流程
所有元素分别作为⾸位元素进⾏处理在之后的位置上同理选择所有元素分别作为当前位置元素进⾏处理为避免计算重复组合规定选择之后位置的元素时必须⽐前⼀个元素⼤这样就不会有重复的组合 [1,2]和[2,1]中[2,1]不会出现。
class Solution {
public:bool check[20];vectorvectorint it;vectorint flag;void dfs(int n, int k, int first) {if (k) {for (int i first; i n; i) {flag.push_back(i);dfs(n, k-1,i1);flag.pop_back();}}else{it.push_back(flag);}}vectorvectorint combine(int n, int k) {dfs(n, k, 1);return it;}
};
