csp信奥赛C++标准模板库STL案例应用25
prev_permutation实践
题目描述
排列与组合是常用的数学方法，其中组合就是从n nn个元素中抽出r rr个元素（不分顺序且r ≤ n r \le nr≤n），我们可以简单地将n nn个元素理解为自然数1 , 2 , … , n 1,2,\dots,n1,2,…,n，从中任取r rr个数。
现要求你输出所有组合。
例如n = 5 , r = 3 n=5,r=3n=5,r=3，所有组合为：
123 , 124 , 125 , 134 , 135 , 145 , 234 , 235 , 245 , 345 123,124,125,134,135,145,234,235,245,345123,124,125,134,135,145,234,235,245,345。
输入格式
一行两个自然数n , r ( 1 < n < 21 , 0 ≤ r ≤ n ) n,r(1<n<21,0 \le r \le n)n,r(1<n<21,0≤r≤n)。
输出格式
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
注意哦！输出时，每个数字需要3 33个场宽。以 C++ 为例，你可以使用下列代码：
cout<<setw(3)<<x;输出占3 33个场宽的数x xx。注意你需要头文件iomanip。
输入输出样例 1
输入 1
5 3输出 1
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5思路分析
这段代码使用了STL中的prev_permutation函数和0-1位标记法来生成组合。主要思路是：
二进制位标记法：用一个长度为n的数组a，前r个位置设置为1（表示选中），其余位置为0（表示不选中）。例如n=5, r=3时，初始数组为[1,1,1,0,0]。
利用
prev_permutation：该函数生成当前序列的上一个字典序排列。由于初始序列是降序（1在前，0在后），通过不断获取前一个排列，可以得到所有不同的组合方式。输出组合：对每个排列，输出值为1的位置对应的数字（i+1，因为题目从1开始计数）。
字典序输出：
prev_permutation按照降序生成排列，但输出时我们按索引升序读取，因此组合内部从小到大排列，整体组合也按字典序输出。
代码实现
#include<bits/stdc++.h>// 包含所有标准库usingnamespacestd;intn,r;// n: 总元素个数, r: 要选择的元素个数intmain(){cin>>n>>r;// 读取输入// 创建一个长度为n的vector，前r个元素为1，其余为0// 例如n=5,r=3时：a = [1,1,1,0,0]vector<int>a(n,0);for(inti=0;i<r;i++){a[i]=1;// 前r位标记为1（选中）}// 使用do-while确保至少执行一次，输出初始组合do{// 遍历数组a，输出所有标记为1的位置对应的数字for(inti=0;i<n;i++){if(a[i]){// 如果该位置被选中// 使用setw(3)设置场宽为3，输出i+1（题目要求数字从1开始）cout<<setw(3)<<i+1;}}cout<<endl;// 每个组合后换行}while(prev_permutation(a.begin(),a.end()));// prev_permutation生成当前序列的上一个字典序排列// 当序列变为完全升序时返回false，循环结束return0;}功能分析
核心算法特点：
- 0-1位标记法：用1表示选择该位置数字，0表示不选择，直观高效。
- STL利用：使用
prev_permutation自动生成所有排列，避免手动递归实现。 - 字典序保证：初始数组a为降序排列（1在前，0在后），
prev_permutation按字典序递减生成排列，但输出时按索引升序读取，恰好得到组合的字典序递增输出。
执行流程：
- 初始化一个n位二进制序列，前r位为1。
- 输出当前1的位置对应的数字组合。
- 生成上一个排列（1向左移动）。
- 重复步骤2-3，直到所有1移到最右侧，排列变为升序。
示例演示（n=5, r=3）：
初始: 1 1 1 0 0 → 输出: 1 2 3
上一个排列: 1 1 0 1 0 → 输出: 1 2 4
上一个排列: 1 1 0 0 1 → 输出: 1 2 5
…
直到: 0 0 1 1 1 → 输出: 3 4 5
时间复杂度：
prev_permutation的时间复杂度：O(n)- 总组合数：C(n,r) = n!/(r!(n-r)!)
- 总时间复杂度：O(C(n,r) * n)
空间复杂度：
- O(n) 用于存储标记数组
优点：
- 代码简洁，利用STL减少错误
- 自动按字典序生成组合
- 输出格式符合题目要求
注意：
- 使用
prev_permutation需要包含<algorithm>头文件 - 初始数组必须是降序排列才能生成所有组合
- 数字从1开始，因此输出时是i+1
完整系列资料，请查看专栏：《csp信奥赛C++标准模板库STL》
https://blog.csdn.net/weixin_66461496/category_13108077.html
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}- 一、CSP信奥赛C++通关学习视频课：
- C++语法基础
- C++语法进阶
- C++算法
- C++数据结构
- CSP信奥赛数学
- CSP信奥赛STL
- 二、CSP信奥赛C++竞赛拿奖视频课：
- 信奥赛csp-j初赛高频考点解析
- CSP信奥赛C++复赛集训课（12大高频考点专题集训）
- 三、考级、竞赛刷题题单及题解：
- GESP C++考级真题题解
- CSP信奥赛C++初赛及复赛高频考点真题解析
- CSP信奥赛C++一等奖通关刷题题单及题解
详细内容：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
3、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
- 2025 csp-j 复赛真题及答案解析（最新更新）
- 2025 csp-x(山东) 复赛真题及答案解析（最新更新）
- 2025 csp-x(河南) 复赛真题及答案解析（最新更新）
- 2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
- 2025 csp-x(江西) 复赛真题及答案解析（最新更新）
- 2025 csp-x(广西) 复赛真题及答案解析（最新更新）
- 2020 ~ 2024 csp 复赛真题题单及题解
- 2019 ~ 2022 csp-j 初赛高频考点真题分类解析
- 2021 ~ 2024 csp-s 初赛高频考点解析
- 2023 ~ 2024 csp-x (山东)初赛真题及答案解析
- 2024 csp-j 初赛真题及答案解析
- 2025 csp-j 初赛真题及答案解析（最新更新）
- 2025 csp-s 初赛真题及答案解析（最新更新）
- 2025 csp-x (山东)初赛真题及答案解析(最新更新)
- 2025 csp-x (江西)初赛真题及答案解析(最新更新)
- 2025 csp-x (辽宁)初赛真题及答案解析(最新更新)
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
- 129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图
4、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
