全排列算法解析完整版.doc

全排列算法解析完整版
全排列算法解析完整版
全排列算法解析完整版
全排列以及相关算法
在程序设计过程中，我们往往要对一个序列进行全排列或者对每一个排列进行分析。全排列算法便是用于产生全排列或者逐个构造全排列的方法。当然,全排列算法不仅仅止于全排列，对于普通的排列，或者组合的问题,也可以解决。本文主要通过对全排列以及相关算法的介绍和讲解、分析,让读者更好地了解这一方面的知识,主要涉及到的语言是Ｃ和C+＋．
本文的节数:
全排列的定义和公式:
2。时间复杂度:
3．列出全排列的初始思想:
:
5。全排列算法:
6．全排列的字典序:
７．求下一个字典序排列算法:
8。C＋+　ＳTＬ库中的next_permｕtatｉoｎ（)函数：(＃iｎcluｄe<algoｒitｈm>)
９．字典序的中介数,由中介数求序号：
由中介数求排列:
递增进位制数法:
递减进位制数法:
邻位对换法：
邻位对换法全排列：
邻位对换法的下一个排列:
邻位对换法的中介数:
１７。组合数的字典序与生成：
由于本文的，内容比较多,所以希望读者根据自己的要求阅读,不要一次性读完，有些章节可以分开读。第1节到第5节提供了全排列的概念和一个初始的算法。第６节到第8节主要讲述了字典序的全排列算法。第9到第10节讲了有关字典序中中介数的概念。第１1到第12节主要介绍了不同的中介数方法,仅供扩展用。第１3节到15节介绍了邻位对换法的全排的有关知识。1６节讲了有关邻位对换法的中介数，。
全排列算法解析完整版
全排列算法解析完整版
全排列算法解析完整版
1。全排列的定义和公式:
从n个数中选取ｍ（m＜＝n)个数按照一定的顺序进行排成一个列,叫作从n个元素中取ｍ个元素的一个排列。由排列的定义,显然不同的顺序是一个不同的排列。从ｎ个元素中取m个元素的所有排列的个数,称为排列数。从n个元素取出n个元素的一个排列，称为一个全排列。全排列的排列数公式为ｎ！，通过乘法原理可以得到.
：
n个数（字符、对象)的全排列一共有n!种，所以全排列算法至少时Ｏ（n!）的。如果要对全排列进行输出,那么输出的时间要O(n*ｎ!）,因为每一个排列都有ｎ个数据。所以实际上,全排列算法对大型的数据是无法处理的,而一般情况下也不会要求我们去遍历一个大型数据的全排列。
3。列出全排列的初始思想:
解决一个算法问题，我比较****惯于从基本的想法做起,我们先回顾一下我们自己是如何写一组数的全排列的：1，3，5,９(为了方便，下面我都用数进行全排列而不是字符)。
1,3，5，9.(第一个)
首先保持第一个不变,对3,5，9进行全排列。
同样地,我们先保持３不变,对５,９进行全排列。
保持5不变,对９对进行全排列，由于９只有一个，它的排列只有一种：,5,９相互交换，得到
全排列算法解析完整版
全排列算法解析完整版
全排列算法解析完整版
1,３,９,5.
此时5,９的情况都写完了,不能以3打头了，得到
1，5,3,9
1，5，9，3
1,9,3,５
1，９，5,3
这样,我们就得到了1开头的所有排列,这是我们一般的排列数生成的过程。再接着是以3、5、9打头，得到全排列。这里还要注意的一点是,对于我们人而言，我们脑子里相当于是储存了一张表示原有数组的表,1,3，５,9,1开头的所有排列完成后,我们选择３开头，3选完了之后,我们选择５开头，而不会再返过来选1，而且知道选到９之后结束,但对于计算机而言,我们得到了３，５,１，9后,可能再次跳到1当中,因为原来数组的顺序它已经不知道了，这样便产生了错误。对于算法的设计,我们也可以维护这样一个数组,它保存了原始的数据,这是一种方法。同时我们还可以再每次交换后再交换回来,变回原来的数组,这样程序在遍历的时候便不会出错。读者可以练****一下这个过程,思考一下你是如何进行全排列的,当然,你的方法可能和我的不太一样。
我们把上面全排列的方法归纳一下,基本上就是:任意选一个数(一般从小到大或者从左到右）打头,对后面的ｎ-1个数进行全排列．聪明的读者应该已经发现，这是一个递归的方法,因为要得到ｎ—１个数的全排列,我们又要先去得到ｎ—２个数的全排列,而出口是只有１个数的全排列,因为它只有1种,为它的本身。写成比较规范的流程：
开始ｆoｒ循环．
改变第一个元素为原始数组的第一个元素(什么都没做)。
求第２个元素到第n个元素的全排列。
要求第2个元素到第ｎ个元素的全排列,要递归的求第３个元素到第n个元素的全排列。
全排列算法解析完整版
全排列算法解析完整版
全排列算法解析完整