算法问题之全排列

大家好，欢迎来到IT知识分享网。

一.DFS(递归+回溯）

原题题目：

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式

共一行，包含一个整数 n。

输出格式

按字典序输出所有排列方案，每个方案占一行。

输入样例：

3

输出样例：

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

DFS方法代码如下图：C++版

#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 10; int n, path[N]; //存放排序的结果 bool st[N]; // 创建一个布尔类型数组，用于记录数字是否被使用过 void dfs(int u) // 第几个数字，一共几个数字 { if (u == n)// 递归到最后一个数字 { for (int i = 0; i < n; i++) cout << path[i] << ' '; // 输出path数字中存储的结果 puts(" "); } for (int i = 1; i <= n; i++) if (!st[i]) // 判断数字有没有被用过 { path[u] = i; st[i] = true; // i被用过 dfs(u + 1); // 走到下一层 st[i] = false; // 恢复原样 } } int main() { cin >> n; dfs(0); return 0; } 

大概的流程图如下：（电脑画的，各位客官凑合看）

DFS特点是“不撞南墙不回头”，一路递归到底，然后进行回溯。按树的结构来说就是，一个分支往下走到底，走到没有节点为止，然后回溯，走上一个节点的另一条分支，之后以此类推。

二.c++库函数next_permutation（全排列函数）

代码如下图：

#include<bits/stdc++.h> //顺便提一嘴，这个万能头是Mingw编译器才能用的 using namespace std; int main() { int n; cin>>n; int a[n]; for(int i=0;i<n;i++) a[i]=i+1; do{ for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; }while(next_permutation(a,a+n)); return 0; }

下面讲一下这个next_permutation()函数用法：

1.默认排序 next_permutation(地址，末尾地址+1）；//默认升序排列

2.自定义排序 next_permutation(地址，末尾地址+1，cmp）；//cmp是自定义的排序函数

一般和do-while语句使用，具体如下：

do { }while(next_permutation(//地址，//地址)，//自定义函数，可无)；

以上就是关于全排列的两种方法。

也可以在我的CSDN博客内看 全排列问题-CSDN博客