全排列的生成算法（精编版）.docx

全排列的生成算法全排列的生成算法就是对于给定的字符集 , 用有效的方法将所有可能的全排列无重复无遗漏地枚举出来任何 n 个字符集的排列都可以与 1~n 的 n 个数字的排列一一对应，因此在此就以ｎ个数字的排列为例说明排列的生成法n 个字符的全体排列之间存在一个确定的线性顺序关系 所有的排列中除最后一个排列 外, 都有一个后继；除第一个排列外，都有一个前驱每个排列的后继都可以从 它 的前驱经过最少的变化而得到，全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法 ? 全排列的生成法通常有以下几种 : ? 字典序法 ? 递增进位数制法 ? 递减进位数制法 ? 邻位交换法 ? 递归类算法１．字典序法字典序法中 , 对于数字 1、２、3. ．... ．n 的排列 , 不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的 例如对于 5 个数字的排列 12354 和 1２３ 45，排列 12345在前 , 排列 123５４在后按照这样的规定 ,5 个数字的所有的排列中最前面的是 123４ 5， 最后面的是 5432１ ? 字典序算法如下 : ? 设Ｐ是 1~ｎ的一个全排列 :ｐ =p1p2． ． . ． .pn ＝ p1ｐ 2． . ． . ．. ｐ j-1p ｊｐ j+1.. ．...p ｋ -1pk ｐｋ +1.. ．... ｐ n? １ ) 从排列的右端开始 , 找出第一个比右边数字小的数字的序号 j （ j 从左端开始计算) ，即 j= ｍ ax{i|pi

pj} （右边的数从右至左是递增的，因此 k 是所有大于 pj 的数字中序号最大者） ? 3) 对 换 pi,pk4) 再将 pj+1.. ． ...pk － 1 ｐ kpk ＋ 1 ｐ n 倒转得到排列 p ’’ =ｐ 1p2.. ． ..pj-1pjpｎ .....pk+1p ｋ pk- １ .....p ｊ+1，这就是排列 p 的下一个下一个排列。

? 例如 839６ 47521 是数字 1~9 的一个排列从它生成下一个排列的步骤如下： ? 自右至左找出排列中第一个比右边数字小的数字４ 83 ９ 647521在该数字后的数字中找出比 4 大的数中最小的一个 5 ８ 3９ 647521将５与 4 交换 83 ９ 657421将 74２1 倒转 8３ 9６ 5124７所以８ 39６４ 75２ 1 的下一个排列是８ 396512472. 递增进位数制法在递增进位制数法中 , 从一个排列求另一个排列需要用到中介数 如果用 ｋ i 表示排列 p1p2...pi ． .p ｎ中元素 pｉ的右边比 pi 小的数的个数，则排列的中介数就是对应的排列 k1 ． . ． ... ki.... ． . k ｎ－ 1 例如排列 8３964７ 521 的中介数是 7264２ 3２ 1,7 、2、6、.... ． 分别是排列中数字８、 ３、9、.... ．. 的右边比它小的数字个数 ? 中介数是计算排列的中间环节已知一个排列 , 要求下一个排列，首先确定其中介数 , 一个排列的后继 , 其中介数是原排列中介数加 1, 需要注意的是 , 如果中介数的末位ｋｎ－ 1＋ 1＝ ２， 则要向前进位， 一般情形 , 如果 ki+1=n- ｉ＋１ , 则要进位， 这就是所谓的递增进位制。

例如排列 8３ 9６４７５ 21 的中介数是 72642 ３２ 1, 则下一个排列的中介数是 673４2221+1=673４ 2３ 00( 因为 1+1＝ 2，所以向前进位， 2+1=3, 又发生进位， 所以下一个中介数是 6７３ 42300）得到中介数后 , 可根据它还原对应得排列 ? 算法如下：--中介数 k1、ｋ 2、.. ． ．. 、kn-1 的各位数字顺序表示排列中的数字 n、ｎ－１、． 、2 在排列中距右端的的空位数，因此 , 要按 k1、k ２、...... 、ｋ n-1 的值从右向左确定 n、ｎ -1 、...... 、2 的位置，并逐个放置在排列中： i 放在右起的 kｉ +1 位，如果某位已放 有数字，则该位置不算在内 , 最后一个空位放１ ? 因此从 6７３４ 23０ 0 可得到排列８ 4９ 61７ 523，它就是 8３９ 6４ 7５ 2１的后一个排列因为 9 最先放置， k1=６， 9 放在右起第 7 位，空出 6 个空位， 然后是放 8, ｋ２＝ 7, ８放在右起第 8 位, 但 9 占用一位 , 故 8 应放在右起第 9 位, 余类推３. 递减进位制数法在递增进位制数法中 , 中介数的最低位是逢 2 进 1, 进位频繁 , 这是一个缺点。

把递增进位制数翻转 , 就得到递减进位制数 83 ?９６ 47５ 21 的中介数是 673４２ 22１(k1k2... ｋn-1), 倒转成为 122２437６（ kｎ -1...k ２ k1) ，这是递减进位制数的中介数 :ki( ｉ =n- １, ｎ－ 2,...,2) 位逢 i 向 ki －1 位进１ 给定排列 p,p 的下一个排列的中介数定义为 p 的中介数加 1例如 p＝８ 3９ 64752１， p 的中介数为 122２ 437６，p 的下一个排列的中介数为12２ 24３ 7６ +1=12２2４ 377, 由此得到 p 的下一个排列为８９ 3647521 给定中介数， 可用与递增进位制数法类似的方法还原出排列但在递减进位制数中，可以不先计算中介数就直接从一个排列求出下一个排列具体算法如下：1 ）如果 p( ｉ ) ＝ n 且 i<>n ，则 p（ｉ ) 与ｐ (i- １）交换 ? 2）如果 p（ n)=n, 则找出一个连续递减序列９、 8、.. ． ... 、ｉ , 将其从排列左端删除 , 再以相反顺序加在排列右端 , 然后将 i-1 与左边的数字交换 ? 例如 p＝ 8936４７ 52１的下一个排列是 9８３ 6４ 7521。

求 983647 ５21 的下一个排列时 , 因为 9 在最左边且第２位为 8，第 3 位不是 7，所以将 8和９从小到大排于最右端３ 64752１８ 9, 再将 7 与其左方数字对调得到 9８３ 64７ 521 的下一个排列是３ 6745218９又例如求 9８ 76３ 5４ 21 的下一个排列 , 只需要将 9876 从小到大排到最右端并将 5 与其左方数字３对调 , 得到 534２ 1６７ 8９4. 邻位对换法邻位对换法中下一个排列总是上一个排列某相邻两位对换得到的以 4 个元素的排列为例 , 将最后的元素 4 逐次与前面的元素交换 , 可以生成 4 个新排列：3 2 1 ? ４ １ 2 4 ３１ ４ 2 3 ４ １ 2 3 ? 然后将最后一个排列的末尾的两个元素交换 , 再逐次将排头的4 与其后的元素交换，又生成四个新排列 : ? 4 1 3 ２ 1 4 3 2 1 3 ４ 2 1 ３ 2 4? 再将最后一个排列的末尾的两个元素交换，将 4 从后往前移：３ １ ２ 4 3 1 4 2 3 4 １ 2 4 3 1 2如此循环既可求出全部排列5. 元素增值法（ n 进制法)1）从原始排列ｐ =p１ｐ２ .. ． ...pn 开始 , 第 n 位加ｎ－ 1, 如果该位的值超过 n，则将它除以 n，用余数取代该位，并进位（将第 n-1 位 加 1)2) 再按同样方法处理 n- １位，ｎ -2 位， ... ．.. ，直至不再发生进位为止，处理完一个排列就产生了一个新的排列ｎ则结束3 ?) 将其中有相同元素的排列去掉4 ?）当第一个元素的值 >以 3 个数 1、2、３的排列为例 : 原始排列是 1 2 ３ , 从它开始 , 第 3 个元素是 3,3+2=５，５ Mod 3=２，第 2 个元素是 2，2＋１ =3，所以新排列是 1 ３ ２。

通过元素增值 ,顺序产生的排列是：１ 2 3,1 3 ２ ,2 1 1,2 1 3 ，２ 2 2 ，２ 3 １ ,2 ３ 3, ３ １2,3 2 １有下划线的排列中存在重复元素 , 丢弃 , 余下的就是全部排列6. 递归类算法全排列的生成方法用递归方式描述比较简洁 , 实现的方法也有多种1 ）回溯法 ? 回溯法通常是构造一颗生成树以 3 个元素为例；树的节点有个数据， 可取值是１、２、３如果某个为０，则表示尚未取值 ? 初始状态是（０ ,0,0 ），第１ 个元素值可以分别挑选 1，2,3 ，因此扩展出 3 个子结点用相同方法找出这些结点的第 2个元素的可能值 , 如此反复进行，一旦出现新结点的 3 个数据全非零，那就找到了一种全排列方案当尝试了所有可能方案，即获得了问题的解答2）递归算法如果用 P 表示 n 个元素的排列， 而Ｐ i 表示不包含元素ｉ的排列 ,( ｉ )Pi 表示在排列 P ｉ前加上前缀 i 的排列， 那么 , ｎ个元素的排列可递归定义为 : ? 如果 n=1, 则排列Ｐ只有一个元素 i如果 n>1，则排列 P 由排列 (i ）Ｐ i 构成 (i=1 、2、. ． .. 、n－ 1) 。

根据定义 , 容易看出如果已经生成了ｋ -1 个元素的排列， 那么， ｋ个元素的排列可以在每个 k-1 个元素的排列 Pｉ前添加元素ｉ而生成例如２个元素的排列是 1 ２和 2 1，对与个元素而言，ｐ1 是 2 ３和３ 2, 在每个排列前加上１即生成１ 2 3 和 1 3 ２两个新排列， p2 和 p３则是１ 3 、3 1 和 1 2、2 1，按同样方法可生成新排列 2 1 3、２ ３ 1 和３ 1 ２、３ ２ １。