全排列算法重复

⑴ 全排列的生成树

可以采用树的结构表示全排列生成算法，以数字的全排列生成算法为例，从最小的数1开始，其全排列只有一种可能；加入数字2，数字2可以插入在1的后边或前边，有两个不同位置；
再加入3，对于第二层中的每一种不同排列，都可以通过将3插入不同位置得到三种不同的排列数，共有6种排列数；一次类推可以得到 个数的全排列。
基于此，可以构造一种新的中介数，其定义如下：
对于生成树中的第n层，每一个节点中介数的前n-2位继承于其父节点的中介数，中介数最后一位为该层新加入的数 减去其右边相邻的数。
如果新加入的数在最右边，则中介数最后一位为0。
如图所示，排列数12的中介数为0，对于生成树第三层由节点12扩展得到的新节点，当新加入的数3位于最右边时（即排列数123），对应的中介数为00；若3插入12中间，则中介数末位为3-2=1，即中介数为01；类似地排列数312对应的中介数为02。
不难看出，生成树中介数也是递减进位制数，但和递减进位制数法是不同的。如排列数231对应的生成树中介数为12，而递减进位制数法对应的中介数为11。 不难看出，全排列生成树每一层的不同节点对应的中介数都是不同的，这是因为：
（1）每个子节点中介数的前缀都从其父节点继承得到，因此不同父节点生成的子节点中介数一定不同；
（2）同一个父节点生成的子节点，父节点的排列数每一位都是不同的，因此新加入的数插入不同位置得到的中介数的最后一位一定是不同的。
由以上两点及归纳法即可证明生成树每一层不同节点对应的中介数都是唯一不重复的。又全排列生成树每一个节点的排列数是无重复无遗漏的，因此从中介数到排列数的映射是一一对应的，从而基于生成树中介数的全排列生成算法是完备的。 由生成树中介数还原排列数的过程实际上就是全排列生成树的构建过程。以生成树中介数121为例：
（1）中介数第一位是1，说明2在1的左边，得到21；
（2）中介数第二位为2，只能由3-1得到，说明3在1的左邻，得到231；
（3）中介数第三位为1，只能由4-3得到，说明4在3的左邻，得到2431.
对于任意的生成树中介数，都通过类似的过程计算对应的排列数。不难看出，从生成树中介数还原排列数的时间复杂度也是 。

⑵ 关于全排列的算法问题

最低0.27元/天开通网络文库会员，可在文库查看完整内容>
原发布者:ON9V4Xr2gU9J7
全排列以及相关算法在程序设计过程中，我们往往要对一个序列进行全排列或者对每一个排列进行分析。全排列算法便是用于产生全排列或者逐个构造全排列的方法。当然，全排列算法不仅仅止于全排列，对于普通的排列，或者组合的问题，也可以解决。本文主要通过对全排列以及相关算法的介绍和讲解、分析，让读者更好地了解这一方面的知识，主要涉及到的语言是C和C++。本文的节数：1.全排列的定义和公式：2.时间复杂度：3.列出全排列的初始思想：4.从第m个元素到第n个元素的全排列的算法：5.全排列算法：6.全排列的字典序：7.求下一个字典序排列算法：8.C++STL库中的next_permutation()函数：（#include）9.字典序的中介数，由中介数求序号：10.由中介数求排列：11.递增进位制数法：12.递减进位制数法：13.邻位对换法：14.邻位对换法全排列：15.邻位对换法的下一个排列：16.邻位对换法的中介数：17.组合数的字典序与生成：由于本文的，内容比较多，所以希望读者根据自己的要求阅读，不要一次性读完，有些章节可以分开读。第1节到第5节提供了全排列的概念和一个初始的算法。第6节到第8节主要讲述了字典序的全排列算法。第9到第10节讲了有关字典序中中介数的概念。第11到第12节主要介绍了不同的中介数方法，仅供扩展用。第13节到15节介绍了邻位对换法的全排的有关知识。16节讲了有关邻位对换法的中介数，仅供参考。第17节讲了

⑶ 10的全排列怎么表示

10的全排列表示为10！。全排列，是指从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列，当m=n时所有的排列的叫法。可以采用树的结构表示全排列生成算法。递减进位制数法的中介数进位不频繁，求下一个排列在不进位的情况下很容易。公式为全排列数f(n)=n(定义0=1）。