C++全排列中递归交换法的示例分析-创新互联

这篇文章主要介绍了C++全排列中递归交换法的示例分析,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。

创新互联是一家专注于成都做网站、网站设计与策划设计,杨浦网站建设哪家好?创新互联做网站,专注于网站建设10年,网设计领域的专业建站公司;建站业务涵盖:杨浦等地区。杨浦做网站价格咨询:028-86922220

对于求解全排列问题有最暴力的递归枚举法,但是我们希望可以优化时间,因此出现了递归交换法。

例题

洛谷1706

题目描述

输出自然数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 
# include 
# include 
# include 

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++全排列中递归交换法的示例分析”这篇文章对大家有帮助,同时也希望大家多多支持创新互联建站,关注创新互联网站建设公司行业资讯频道,更多相关知识等着你来学习!

另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


网站名称:C++全排列中递归交换法的示例分析-创新互联
文章URL:http://myzitong.com/article/dhphpj.html