全排列是蓝桥杯中的高频考点之一，接下来为我的学习历程：
先练习基本的全排列 -> 熟练应用后套用stl函数库->进阶练习
3、C++模板函数套用
1、全排列 - 基础练习
给定一个不含重复数字的数组
nums，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
提示：
1 <= nums.length <= 6-10 <= nums[i] <= 10nums中的所有整数 互不相同
// 本题格式是，力扣的独有格式。 // 本题通过递归进行,全排列 class Solution { // 各处存数据的数组 vector<vector<int>> res; vector<int> cur; void generate(vector<int>& nums, vector<bool>& userd){ if(cur.size()==nums.size()){ res.push_back(cur); return; } for(int i=0; i<userd.size(); ++i){ if(!userd[i]){ // 如果未被使用过 userd[i] = true; cur.push_back(nums[i]); generate(nums,userd); cur.pop_back(); userd[i] = false; } } } public: vector<vector<int>> permute(vector<int>& nums) { res.clear(); cur.clear(); vector<bool> userd(nums.size(),false); generate(nums,userd); return res; } };
2、全排列II - 基础练习
给定一个可包含重复数字的序列
nums，按任意顺序 返回所有不重复的全排列。示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8-10 <= nums[i] <= 10
class Solution { public: vector<vector<int>> res; vector<int> cur; void generate(vector<int>& nums, vector<bool>& used){ if(cur.size()==nums.size()){ res.push_back(cur); return; } for(int i = 0; i<nums.size(); i++){ if(!used[i]){ if(i>0&&!used[i-1]&&nums[i]==nums[i-1]) continue; // 跳过是精华核心，每次递归到同一档次的时候，就直接跳过。 used[i]=true; cur.push_back(nums[i]); generate(nums,used); cur.pop_back(); used[i]=false; } } } vector<vector<int>> permuteUnique(vector<int>& nums) { res.clear(); cur.clear(); sort(nums.begin(),nums.end()); // 排序是本题基础 vector<bool> used(nums.size(),false); generate(nums,used); return res; } };
3、C++模板函数套用
在竞赛中，如果使用dfs进行全排列的话，确实非常麻烦。固，可引用tls库中的内容。
共两种用法，主要：
1、next_permutation(vec.begin(), vec.end());
2、prev_permutation(vec.begin(), vec.end());
#include "bits/stdc++.h" using namespace std; vector<vector<int>> res; vector<int> cur; void generate(vector<int>& vec, vector<bool>& used){ if(cur.size()==vec.size()){ res.push_back(cur); return; } for(int i=0; i<vec.size(); ++i){ if(!used[i]){ used[i]= true; cur.push_back(vec[i]); generate(vec,used); cur.pop_back(); used[i]=false; } } } int main(){ vector<int> vec{1,2,3}; // 全排列 cout<<"------------ 以下是next_permutation生成与输出 ------------------"<<endl; do{ for(int num : vec){ cout<<num<<" "; } cout<<endl; }while(next_permutation(vec.begin(),vec.end())); cout<<"------------ 以下为手写DFS函数的输出 ------------------"<<endl; vector<bool> used(vec.size(), false); generate(vec,used); for(vector<int>& v : res){ for(int num : v){ cout<<num<<" "; } cout<<endl; } return 0; }
下方为输出函数：
------------ 以下是next_permutation生成与输出 ------------------ 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 ------------ 以下为手写DFS函数的输出 ------------------ 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
4、排列序数（蓝桥真题）
题目描述
如果用 a b c d 这 4 个字母组成一个串，有 4!=24 种，如果把它们排个序，每个串都对应一个序号：
abcd 0
abdc 1
acbd 2
acdb 3
adbc 4
adcb 5
bacd 6
badc 7
bcad 8
bcda 9
bdac 10
bdca 11
cabd 12
cadb 13
cbad 14
cbda 15
cdab 16
cdba 17
⋯⋯
现在有不多于 10 个两两不同的小写字母，给出它们组成的串，你能求出该串在所有排列中的序号吗？
输入描述
输入一行，一个串。
输出描述
输出一行，一个整数，表示该串在其字母所有排列生成的串中的序号。注意：最小的序号是 0。
输入输出样例
示例
输入
bdca
输出
11
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
#include "bits/stdc++.h" using namespace std; int main(){ string str,strx; cin>>str; strx=str; sort(str.begin(),str.end()); int ans=0; do { if(strx==str){ break; } ans++; }while(next_permutation(str.begin(),str.end())); cout<<ans<<endl; return 0; ----------------- 以下为本题拓展 ----------------- 1、sort 能遍历快速模板 使用了内省排序，内省排序结合了快速排序（Quicksort）、堆排序（Heapsort） 和插入排序（Insertion sort）的优点。它以快速排序为基础，在递归深度达到一定 阈值（通常是 ， 为元素数量）时，为避免快速排序在最坏情况下（ 时间复杂度）的 性能问题，会切换到堆排序；在处理小规模数据（通常是元素数量少于 16 个）时，会 使用插入排序，因为插入排序在处理小规模数据时效率较高。 2、sort 能够排列 数组{sort(arr,arr+size)}、自定义容器、vector、deque等
5、带分数 - 真题（蓝桥真题）
带分数
题目描述
100 可以表示为带分数的形式：100 = 3 + 69258 / 714
还可以表示为：100 = 82 + 3546 / 197
注意特征：带分数中，数字 1~9 分别出现且只出现一次（不包含 0 ）。
类似这样的带分数，100 有 11 种表示法。
输入描述
从标准输入读入一个正整数 N (N<1000×1000)N (N<1000×1000)。
输出描述
程序输出该数字用数码 1~9 不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！
输入输出样例
示例
输入
100
输出
11
#include <iostream> #include <vector> #include <algorithm> using namespace std; int generate(const vector<int>& vec, int st, int en){ int sum = 0; for(int i = st; i<=en; i++){ // 求和 sum = sum*10 + vec[i]; } return sum; } int main(){ int num; cin >> num; vector<int> vec{ 1,2,3,4,5,6,7,8,9 }; // 排列是什么 // 分成三个点，分别对每个点 vector<int> num1; vector<int> num2; vector<int> num3; int n1,n2,n3; int flag = 0; do{ // 直接套三个循环会极其不合理。 for(int i=0; i<vec.size()-2; ++i){ n1 = generate(vec,0,i); for(int j=i+1; j<vec.size()-1; ++j){ n2 = generate(vec,i+1,j); n3 = generate(vec,j+1,8); if(num*n3==n1*n3+n2) flag++; // 如果这里用，num == n1 + n3/n3; 是不对的，因为这样会造成精度损失 } } }while(next_permutation(vec.begin(), vec.end())); cout<<flag<<endl; // 请在此输入您的代码 return 0; } -------------------------------------------------------- 原本错误的写法，用了三重循环，这样是不合理的 -------------------------------------------------------- /* vector<int> num1; vector<int> num2; vector<int> num3; int n1,n2,n3; int flag = 0; do{ for(int i=0; i<num.size()-2; ++i){ num1.push_back(vec[i]); n1 = generate(num1); num2.clear(); for(int j=i+1; j<num.size()-1; ++j){ num2.push_back(vec[j]); num2 = generate(num2); num3.clear(); for(int z=j+1; z<num.size(); ++z){ num3.push_back(vec[z]); n3 = generate(num3); } if(n1>num) break; if((n1+n2/n3==num) flag++; } } }while(next_permutation(vec.begin(), vec.end())); */ --------------------------------------------------------
按照以上可基本掌握基础的全排列，方便进阶学习。
如有错误，私信我，定及时更改。
