今天小编给大家分享一下C++全排列中递归交换法怎么用的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。
题目描述
输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
输入格式
一个整数n。
输出格式
由1～n组成的所有不重复的数字序列，每行一个序列。
每个数字保留 5个场宽。
输入样例
3
输出样例
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
全排列问题——递归交换法
其实跟暴力枚举思路差不多，每次递归枚举第x个数字是几，之后a[x]可以选择不动，也可以选择与后面任意一个数交换位置，就是从后面选一个数放到x的位置上。
简而言之，就是每到一位就从后面选一个尚未被使用过的数字与该位数字交换，这里有些难理解，您可以自己按照程序推一下样例。
这样我们就可以打印所有的全排列了，但这样不是按顺序打印，所以这里需要每次对a[x] ~ a[n]进行排序。
举个例子，如对1、2、3进行全排列。当我们交换1和3后，序列变为3、2、1，如果说这里不排序，直接2、1都保持不动，就输出3、2、1了，可是我们先要的应该是3、1、2，所以要进行排序。
最后，算一下时间复杂度，我们发现需要从1到n一位一位的看，之后每位还要枚举x ~ n，所以总时间复杂度为O(n!)。
代码
计算
安全
数据库
网络和加速
企业服务
# include <cstdio>
# include <cmath>
# include <cstring>
# include <algorithm>
using namespace std;
const int N_MAX = 10;
int n;
int a[N_MAX + 10];
void permutation(int x)
{
if (x == n) {
for (int i = 1; i <= n; i++)
printf("%5d", a[i]);
printf("\n");
return;
}
for (int i = x; i <= n; i++) {
sort(a + x, a + n + 1);
swap(a[x], a[i]);
permutation(x + 1);
swap(a[x], a[i]);
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
a[i] = i;
permutation(1);
return 0;
}以上就是“C++全排列中递归交换法怎么用”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注亿速云行业资讯频道。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://www.xuebuyuan.com/3290788.html
