csp信奥赛C++标准模板库STL案例应用21

csp信奥赛C++标准模板库STL案例应用21

next_permutation实践

题目描述

按照字典序输出自然数1 11到n nn所有不重复的排列，即n nn的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数n nn。

输出格式

由1 ∼ n 1 \sim n1∼n组成的所有不重复的数字序列，每行一个序列。

每个数字保留5 55个场宽。

输入输出样例 1

输入 1

3

输出 1

1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

说明/提示

1 ≤ n ≤ 9 1 \leq n \leq 91≤n≤9。

核心思路

1. 初始化序列：创建包含1到n的有序向量
2. 生成排列：利用next_permutation按字典序生成所有排列
3. 格式输出：使用setw控制输出格式满足题目要求

时间复杂度：O(n! × n)

• 共有n!个排列
• 每个排列输出需要O(n)时间

空间复杂度：O(n)

• 只使用了一个大小为n的向量

代码实现

#include<bits/stdc++.h>// 包含所有标准库头文件（竞赛常用写法）usingnamespacestd;intn;// 全局变量，存储输入的nintmain(){cin>>n;// 读入nvector<int>a;// 创建整型向量a，用于存储当前排列// 初始化向量a为[1, 2, ..., n]for(inti=1;i<=n;i++){a.push_back(i);// 将1到n依次加入向量}// 使用do-while循环生成所有排列// do-while保证至少执行一次，先输出初始排列do{// 输出当前排列for(inti=0;i<n;i++){// 使用setw(5)设置输出宽度为5个字符，右对齐cout<<setw(5)<<a[i];}cout<<endl;// 每个排列后换行// next_permutation将向量a变为字典序的下一个排列// 当没有下一个排列时返回false，循环结束}while(next_permutation(a.begin(),a.end()));return0;}

功能分析

1.输入处理

• 读取一个整数n，范围1≤n≤9
• 较小的n值保证了算法在可接受时间内完成（9! = 362880）

2.排列生成机制

• next_permutation原理：按字典序生成下一个排列
• 初始状态：向量a为升序排列[1,2,…,n]
• 终止条件：当序列变为降序排列时，函数返回false
• 特性：自动处理重复元素（本题中无重复数字）

3.输出格式化

• 场宽控制：setw(5)确保每个数字占5个字符宽度
• 对齐方式：默认右对齐，符合题目要求
• 行格式：每个数字后无额外空格，一行一个排列

4.算法特点

• 简洁性：利用标准库函数，代码量少
• 正确性：按字典序生成所有排列，与题目要求一致
• 通用性：适用于任何可比较的元素类型

示例流程（n=3）：

1. 初始状态：[1,2,3]
2. 第一次循环：输出"1 2 3"
3. next_permutation生成：[1,3,2]
4. 第二次循环：输出"1 3 2"
5. 依此类推，直到[3,2,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;}