C++全排列中递归交换法实例详解
对于求解全排列问题有最暴力的递归枚举法,但是我们希望可以优化时间,因此出现了递归交换法。
例题
洛谷1706
题目描述
输出自然数1到n所有不重复的排列,即n的全排列,要求所产生的任一数字序列中不允许出现重复的数字。
输入格式
一个整数n。
输出格式
由1~n组成的所有不重复的数字序列,每行一个序列。
每个数字保留5个场宽。
输入样例
3
输出样例
123
132
213
231
312
321
全排列问题——递归交换法
其实跟暴力枚举思路差不多,每次递归枚举第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#include #include #include usingnamespacestd; constintN_MAX=10; intn; inta[N_MAX+10]; voidpermutation(intx) { if(x==n){ for(inti=1;i<=n;i++) printf("%5d",a[i]); printf("\n"); return; } for(inti=x;i<=n;i++){ sort(a+x,a+n+1); swap(a[x],a[i]); permutation(x+1); swap(a[x],a[i]); } } intmain() { scanf("%d",&n); for(inti=1;i<=n;i++) a[i]=i; permutation(1); return0; }
以上就是小编给大家整理的全部相关知识点,感谢大家对毛票票的支持。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。