全排列以及相关算法
在程序设计过程中，我们往往要对一个序列进行全排列或者对每一个排列进行分析。
全排列算法便是用于产生全排列或者逐个构造全排列的方法。当然，全排列算法不仅仅止
于全排列，对于普通的排列，或者组合的问题，也可以解决。本文主要通过对全排列以及
相关算法的介绍和讲解、分析，让读者更好地了解这一方面的知识，主要涉及到的语言是
C 和 C++。
本文的节数：
1.全排列的定义和公式：
2.时间复杂度：
3.列出全排列的初始思想：
4.从第 m 个元素到第 n 个元素的全排列的算法：
5.全排列算法：
6.全排列的字典序：
7.求下一个字典序排列算法：
8.C++ STL 库中的 next_permutation()函数：（#include<algorithm>）
9.字典序的中介数，由中介数求序号：
10.由中介数求排列：
11.递增进位制数法：
12.递减进位制数法：
13.邻位对换法：
14.邻位对换法全排列：
15.邻位对换法的下一个排列：
16.邻位对换法的中介数：
17.组合数的字典序与生成：
由于本文的，内容比较多，所以希望读者根据自己的要求阅读，不要一次性读完，有些章
节可以分开读。第 1 节到第 5 节提供了全排列的概念和一个初始的算法。第 6 节到第 8 节
主要讲述了字典序的全排列算法。第 9 到第 10 节讲了有关字典序中中介数的概念。第 11
到第 12 节主要介绍了不同的中介数方法，仅供扩展用。第 13 节到 15 节介绍了邻位对换法
的全排的有关知识。16 节讲了有关邻位对换法的中介数，仅供参考。第 17 节讲了组合数
生成的算法。
1.全排列的定义和公式：
从 n 个数中选取 m（m<=n）个数按照一定的顺序进行排成一个列，叫作从 n 个元素中取 m
个元素的一个排列。由排列的定义，显然不同的顺序是一个不同的排列。从 n 个元素中取
m 个元素的所有排列的个数，称为排列数。从 n 个元素取出 n 个元素的一个排列，称为一
个全排列。全排列的排列数公式为 n!，通过乘法原理可以得到。
2.时间复杂度：
n 个数（字符、对象）的全排列一共有 n!种，所以全排列算法至少时 O(n!)的。如果要对全
排列进行输出，那么输出的时间要 O(n*n!)，因为每一个排列都有 n 个数据。所以实际上，
全排列算法对大型的数据是无法处理的，而一般情况下也不会要求我们去遍历一个大型数
据的全排列。
3.列出全排列的初始思想：
解决一个算法问题，我比较习惯于从基本的想法做起，我们先回顾一下我们自己是如
- 1
- 2
- 3
前往页