全排列生成算法【DOC精选】.doc

全排列的生成算法?对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。?字典序法按照字典序求下一个排列的算法?/*例?字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。注意?一个全排列可看做一个字符串，字符串可有前缀、后缀。*/生成给定全排列的下一个排列所谓一个全排列的下一个排列就是这一个排列与下一个排列之间没有其他的排列。这就要求这一个排列与下一个排列有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。/*例?839647521是1—9的排列。1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。算法: 由 P1P2…Pn 生成的下一个排列的算法如下:1. 求 i=max{j| Pj-1Pj}2. 求 l=max{k| Pi-1Pk }3.?交换Pi-1 与Pl得到P1P2…Pi-1 (P i....Pn ) , 将红色部分顺序逆转,得到结果. 例?求839647521的下一个排列1. 确定i，从左到右两两比较找出后一个数比前一个大的组合，在这里有39 47，然后i取这些组中最到的位置号（不是最大的数）在这两组数中7的位置号最大为6，所以i=62.确定l， 找出在i（包括i）后面的所有比i前面那一位大的数的最大的位置号，在此例中7，5 都满足要求，则选5，5的位置号为7，所以?l=73. 先将4和5交换，然后将5后的四位数倒转得到结果 839657421à?839651247以上算法是在数论课上老师给出的关于字典序全排列的生成算法，以前也经常要用到全排列生成算法来生成一个全排列对所有的情况进行测试，每次都是现到网上找一个算法，然后直接copy代码，修改一下和自己的程序兼容就行了，也不看是怎么来的，不是我不想看，实在是说的很抽象，那一大堆公式来吓人，一个实例都不给，更有甚者连算法都没有，只是在那里说，想看都看不懂，也没那个耐心取理解那些人写出来的那种让人无法忍受的解释。不过在说别人的同时我也知道，自己写的也不够好，不过这就是我的理解了，没法子写的再细了。 全排列的生成算法 2008年04月25日 星期五 下午 03:23 全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。任何n个字符集的排列都可以与1～n的n个数字的排列一一对应，因此在此就以n个数字的排列为例说明排列的生成法。n个字符的全体排列之间存在一个确定的线性顺序关系。所有的排列中除最后一个排列外，都有一个后继；除第一个排列外，都有一个前驱。每个排列的后继都可以从 它 的前驱经过最少的变化而得到，全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。全排列的生成法通常有以下几种：字典序法递增进位数制法递减进位数制法邻位交换法n进位制法递归类算法1.字典序法字典序法中，对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321。字典序算法如下：设P是1～n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn1）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即?? j=max{i|pipi+1}2）在pj的右边的数字中，找出所有比pj大的数中最小的数字pk，即 k=max{i|pipj}（右边的数从右至左是递增的，因此k是所有大于pj的数字中序号最大者）3）对换pi，pk 4）再将pj+1......pk-1pkpk+1pn倒转得到排列p=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这就是排列p的下一个下一个排列。例如839647521是数字1～9的一个排列。从它生成下一个排列的步骤如下： 自右至左找出排列中第一个比右边数字小的数字4 ?? ?? ?? 839647521在该数字后的数字中找出比4大的数中最小的一个5 ?? ??? 839647521将5与4交换 ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? 839657421将7421倒转 ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??