C++全排列中递归交换法实例详解

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

例题

洛谷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 <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;
}

以上就是小编给大家整理的全部相关知识点，感谢大家对我们的支持。

赞 (0)

相关推荐

  • C++全排列中递归交换法实例详解

    对于求解全排列问题有最暴力的递归枚举法,但是我们希望可以优化时间,因此出现了递归交换法. 例题 洛谷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个数字

  • PHP中递归的实现实例详解

    PHP中递归的实现实例详解

    递归的定义 递归(http:/en.wikipedia.org/wiki/Recursive)是一种函数调用自身(直接或间接)的一种机制,这种强大的思想可以把某些复杂的概念变得极为简单.在计算机科学之外,尤其是在数学中,递归的概念屡见不鲜.例如:最常用于递归讲解的斐波那契数列便是一个极为典型的例子,而其他的例如阶层(n!)也可以转化为递归的定义(n! = n*(n-1)!).即使是在现实生活中,递归的思想也是随处可见:例如,由于学业问题你需要校长盖章,然而校长却说"只有教导主任盖章了我才会盖章&

  • C语言中递归和排列组合详解

    目录 排列组合三大问题: 1.打印n个数的全排列 2.打印n个数中任意m个数的全排列 3.打印n个数中任意m个数的组合 完整代码如下: 总结 排列组合三大问题: 1.打印n个数的全排列2.打印n个数中任意m个数的全排列3.打印n个数中任意m个数的组合 1.打印n个数的全排列 这个题实际上是可以直接用STL中的next_permutation()函数,代码如下: #include<bits/stdc++.h> using namespace std; int main(){ int data[4

  • Python 中迭代器与生成器实例详解

    Python 中迭代器与生成器实例详解

    Python 中迭代器与生成器实例详解 本文通过针对不同应用场景及其解决方案的方式,总结了Python中迭代器与生成器的一些相关知识,具体如下: 1.手动遍历迭代器 应用场景:想遍历一个可迭代对象中的所有元素,但是不想用for循环 解决方案:使用next()函数,并捕获StopIteration异常 def manual_iter(): with open('/etc/passwd') as f: try: while True: line=next(f) if line is None: br

  • C语言中联合体union的实例详解

     C语言中联合体union的实例详解 1.定义: union(int i, short s, char c) un; un.i = 3; printf("i=%d",un.i); printf("length = %d\n",sizeof(un);//==4,有最大的变量来决定 2.相当与java里的List T类型 3.数据交换 void swap(int *p , int *q){ int temp = *p; *p = *q; *q = temp; } 4.打

  • Python爬虫包 BeautifulSoup 递归抓取实例详解

    Python爬虫包 BeautifulSoup  递归抓取实例详解 概要: 爬虫的主要目的就是为了沿着网络抓取需要的内容.它们的本质是一种递归的过程.它们首先需要获得网页的内容,然后分析页面内容并找到另一个URL,然后获得这个URL的页面内容,不断重复这一个过程. 让我们以维基百科为一个例子. 我们想要将维基百科中凯文·贝肯词条里所有指向别的词条的链接提取出来. # -*- coding: utf-8 -*- # @Author: HaonanWu # @Date: 2016-12-25 10:

  • Django中的forms组件实例详解

    Form介绍 我们之前在HTML页面中利用form表单向后端提交数据时,都会写一些获取用户输入的标签并且用form标签把它们包起来. 与此同时我们在好多场景下都需要对用户的输入做校验,比如校验用户是否输入,输入的长度和格式等正不正确.如果用户输入的内容有错误就需要在页面上相应的位置显示对应的错误信息.. Django form组件就实现了上面所述的功能. 总结一下,其实form组件的主要功能如下: 生成页面可用的HTML标签 对用户提交的数据进行校验 保留上次输入内容 先在应用目录下my_for

  • Python爬虫包 BeautifulSoup  递归抓取实例详解

    Python爬虫包 BeautifulSoup  递归抓取实例详解 概要: 爬虫的主要目的就是为了沿着网络抓取需要的内容.它们的本质是一种递归的过程.它们首先需要获得网页的内容,然后分析页面内容并找到另一个URL,然后获得这个URL的页面内容,不断重复这一个过程. 让我们以维基百科为一个例子. 我们想要将维基百科中凯文·贝肯词条里所有指向别的词条的链接提取出来. # -*- coding: utf-8 -*- # @Author: HaonanWu # @Date: 2016-12-25 10:

  • JDBC中resutset接口操作实例详解

    本文主要向大家展示JDBC接口中resutset接口的用法实例,下面我们看看具体内容. 1. ResultSet细节1 功能:封锁结果集数据 操作:如何获得(取出)结果 package com.sjx.a; import java.sql.Connection; import java.sql.DriverManager; import java.sql.ResultSet; import java.sql.Statement; import org.junit.Test; //1. next方

  • AngularJS中filter的使用实例详解

    AngularJS中filter的使用实例详解

    AngularJS中filter的使用实例详解 一.格式化数字为货币格式. <div>{{money|currency:"$"}}</div> <div>{{money|currency:"RMB"}}</div> script: app.controller("crl", function($scope, $filter) { $scope.money="4545"; });

随机推荐