组合数学-第一章-排列组合5全排列的生成算法合

1、1.5全排列的生成算法 就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。 全排列的生成算法1.5全排列的生成算法这里介绍全排列算法三种：(A)序数法(B)字典序法(C) 邻位对换法1.5.1 序数法自然数都可以用十进制表示方法表示出来，例如小于 的正整数n可以用下列形式表示出来 推广到p进制数，即例如计算机常常用二进制表示法 1.5.1 序数法用1!, 2!, ,(n-1)!的组合表示小于n!的整数的方法。 可以证明：从0到n!-1的任何整数m可唯一的表示为 其中 也就是说可以证明从0到n!-1的n!个正整数与 一一对 应 其中 .1.5.1 序数法例1 已知m=4

2、000， 6! 40007!求m对应的序列1.5.1 序数法 把n-1个元素的序列 和n个元素的排列建立一一对应关系，从而得到一种生成排列的算法序数法。规则：令n个元素为1，2,n. 是这n个数的任意一个排列，我们可以找到一个序列和它对应，其中 可以看作是排列P中数i+1所在位置右边比i+1小的数的个数。 例 排列3214，它是元素1，2，3，4的一个排列, 它对应的序列是什么？例 序列311对应的排列是什么？1.5.2字典序法 对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。1.5.2字典序法例字符集1,2,3,较小的数字较先,这样

3、按字典序生成的全排列是:123,132,213,231,312,321。 一个全排列可看做一个字符串，字符串可有前缀、后缀。1.5.2字典序法生成给定全排列的下一个排列所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。1.5.2字典序法一般而言，设P是1,n的一个全排列。P=P1P2Pn=P1P2Pj-1PjPj+1Pk-1PkPk+1PnI) j=maxi|PiPjIII) 对换Pj，Pk，IV) 将Pj+1Pk-1PjPk+1Pn翻转，P= P1P2Pj-1PkPnPk+1PjPk-1Pj+1即P的下一个1.5.2

4、字典序法例 839647521是1-9的排列。19的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。1.5.2字典序法求839647521的下一个排列7 5 2 1 747 42 2 41 1 在后缀7521中找出比4大的数7 5找出其中比4大的标号最大的数5 5 5 4 、5 对换 8396 7 2154后缀变为7421 将此后缀翻转 12 4 7接上前缀83965得到839651247 即839647521的下一个。例为后缀大于4的用橙色表示小于4的用绿色表示 找出比右边数字小的标号最大的数4练习求8397635421的下一个排列1.5.3邻位对换法序数法和字典排序法，求下一个排列在不进位的情况下很容易。这就启发我们，能不能设计一种算法，下一个排列总是上一个排列某相邻两位对换得到的。活动状态以12 3 4为初始排列，箭头所指一侧，相邻的数比它小时，则称该数组处在活动状态，1 2 3 4的2，3，4都处于的活动状态。算法步骤（1）若P=P1P2Pn 没有处于活动则结束（2）将处于活动状态的各数中值最大者设为m,则m和它的箭头所指一侧相邻的数互换位置，而且比m大