参考教案成果2013-permutation

1、1 Combinatorics第一章 排列与组合马昱春MA Yuchun 12内容回顾加法法则和乘法法则排列从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。P(n,r) = n(n-1)(n-r+1) = 组合从n个不同的球中,取出r个,放入r个相同的盒子里,每盒1个。C(n,r) = P(n,r)/r! = 模型转换21.4 全排列的生成算法全排列的生成算法：就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。问题的提出：1.排列组合搜索：“我” “是” “马昱春”三个词组的排列排列数： 3! = 6需要列出所有的排列来实现对三个词组的组合检索”我是马昱春

2、” “我 马昱春 是” “是 马昱春 我” “是我马昱春” “马昱春 我是” “马昱春 是我” 2.在旅行商问题中，如何列出所有的方案，找到其中代价最小的?3. 彩票中的排列4. 测试向量的生成？3Generating PermutationsCan we start from the simple thing first?The permutation of 1 1The permutation of 1 2 1 2 2 1The permutation of 1 2 3 1221 23332 13333332 12 12 11 21 21 2333Generate the permutat

3、ions of 1,2,n based on the permutations of 1,2,n-1InductionHigh complexity!Waste of memory!4全排列的生成算法任何n个字符集的排列都可以与1-n的n个数字的排列一一对应，n个数字的全体排列之间存在一个确定的线性顺序关系。“abc”的下一个排列是 “acb” 所有的排列中除最后一个排列外，都有一个后继；除第一个排列外，都有一个前驱。每个排列的后继都可以从它的前驱经过最少的变化而得到全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。5abcacbbaccabcbabca1.5.1字典序法对给定的字

4、符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。例字符集1,2,3,较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。一个全排列可看做一个字符串，字符串可有前缀、后缀。生成给定全排列的下一个排列所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。6这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。123,132,213,231,312,321。从右向左扫描都是增的，就不存在下一个;要找第一次出现下降的位置

5、;2 1 31.5.1字典序法71 2 3?3 2 11 3 2交换？最小的换后面的2 3 1后缀最小比1大的例求839647521的下一个排列1 先找从右到左第一次出现下降的位置42.交换：3.将后缀翻转得到下一个排列是83965124783964752183965742112478396475218找后缀中比4大的最小的数设P是1n的一个全排列: P = p1p2.pn = p1p2.pj-1pjpj+1.pk-1pkpk+1.pn1）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即 j=maxi|pipj（右边的数从右至左是递增的，因此k是所有大于pj的数字

6、中序号最大者）3）对换pi，pk 4）再将pj+1.pk-1pkpk+1.pn倒转得到排列p=p1p2.pj-1pjpn.pk+1pkpk-1.pj+1，这就是排列P的下一个下一个排列。83964752183964752183965742112479计算给定排列的序号全排列的序号即先于此排列的排列的个数。将先于此排列的排列按前缀分类。前缀先于8的排列的个数：78!1*，2*，7*第一位是8,先于83的排列的个数：27!82*,81*前4位是8396,先于83964得的排列的个数：24!前5位是83964,先于839647得的排列的个数：33!前6位是839647,先于8396475得的排列的个

7、数：22!前3位是839,先于8396得的排列的个数：45!前7位是8396475,先于83964752得的排列的个数：11!前2位是83,先于839的排列的个数：66!831*,832*,834*,835*,836*,837*78!+27!+66!+45!+24!+33!+22!+11!= 297191即839647521的序号是 297191，表明839647521前面有297191个排列83964752110123, 132, 213, 231, 312, 321 0 1 2 3 4 5312的序号是？1.5.1字典序法将8!,7!,1!前面的系数抽出，放在一起得到 72642321中介

8、数的特点：记录当前数字右边比当前数字小的数字的个数 72642321是计算排列839647521的序号的中间环节，称之为中介数。78!+27!+66!+45!+24!+33!+22!+11!中介数，序号和排列之间是一一对应的关系。序号是十进制的数，如何从序号得到排列呢？需要利用中介数，来构造排列。839647521前3位是839,先于8396的排列的个数：45!8391*, 8392*, 8394*, 8395*左边前缀用掉了3，因此右边比6小的数字是5-1=4个11构造中介数 7：8的右边比8小的数的个数 2：3的右边比3小的数的个数6：9的右边比9小的数的个数4：6的右边比6小的数的个数2

9、：4的右边比4小的数的个数3：7的右边比7小的数的个数2：5的右边比5小的数的个数1：2的右边比2小的数的个数中介数的特点：记录当前数字右边比当前数字小的数字的个数839647521778!+27!+66!+45!+24!+33!+22!+11!839647521728396475217268396475217264中介数记录了排列中每位数字的排列结构，因此可以用来构造对应的排列。 12由中介数推出排列的算法例 由72642321推算出839647521方法1：P1 P2 P3 P4 P5 P6 P7 P8 P9_ _ _ _ _ _ _ _ _87+1=8 P1 = 82+1=3 P2 =

10、336+1=7，但3小于7已在P3左边出现，7+1=8，但8已在P3左边出现，8+1=9 P3=994+1=5，但3已经在P4左边出现，5+1=6 P4=662+1=3，但3已经在P5左边出现，3+1=4 P4=44751+1=2 P8=2 P9=1 2 1中介数的特点：记录当前数字右边比当前数字小的数字的个数3+1=4，但3,4已经在P6左边出现，4+1+1=6，但6已经在P6左边出现， 6+1=7 P6=72+1=3，但3已经在P7左边出现，3+1=4，但4已经在P7左边出现， 4+1=5 P7=51314打点法算中介数从1-9定位，左边比当前数字大的每个数打点，最终，点的个数意味着右边有

11、多少数比该数小 8 1 9 6 4 7 5 3 21 02 0 0 0 0 0 0 03 0 0 0 0 0 04 0 0 05 0 0 0 06 0 0 7 0 0 8 9 7 0 6 4 2 3 2 1 每个右边的数都给左边的大数贡献一个点141.5.1字典序法0对应的位置，1在最右边打点法：从1-9依次定位，利用点来表示对应位上的数是否比当前数大，点数和当前中介数相等的最左边那一位即当前数所在位置中介数右端加一个0扩成9位每定一位，其左边未定位下加一点从（位位下点数=0）的位中选最左的。7 2 6 4 2 3 2 1定 1 的位置1 2 3上述算法从左到右依次推出中介数。依次定出1,2,

12、3,9的位置。7 2 6 4 2 3 2 1 01定 2 的位置1的下面位位下点数=0 27 2 6 4 2 3 2 1 01定 3 的位置2的下面最左面位位下点数=015016打点法打点法：从1-9依次定位，点数和当前中介数相等的最左边那一位即当前数所在位置中介数右端加一个0扩成9位。从（位位下点数=0）的位中选最左的。每定一位，其左边未定位下加一点。 7 0 6 4 2 3 2 1 02 03 0 0 0 0 0 0 04 0 0 0 0 0 05 0 0 06 0 0 0 07 0 0 8 0 0 123456789定 1 的位置：最左0的下面位位下点数=0定 2的位置： 0的下面位位下

13、点数=0定 3的位置：1的下面位位下点数=0定 4 的位置：2的下面位位下点数=0定 5的位置：2的下面位位下点数=0定 6的位置：4的下面位位下点数=0定 7的位置：3的下面位位下点数=0定 8的位置：7的下面位位下点数=01617字典序下的对应关系排列：P=P1P2Pn n-1序号：ki(n-i)! i=1中介数：k1k2kn-11230(00)1321(01)321n!-1=5 (21)=2*2!+1*1!=5共有n!个排列0到(n!-1)0到(n!-1)个中介数中介数的特点：记录当前数字右边比当前数字小的数字的个数17归纳法证明n-1kk! = n!-1k=11819排列：P=P1P2

14、Pn n-1序号：ki(n-i)! i=1中介数：k1k2kn-11230(00)1321(01)321n!-1=5 (21)=2*2!+1*1!=5共有n!个排列0到(n!-1)0到(n!-1)个中介数字典序中中介数：记录当前数字右边比当前数字小的数字的个数19ki最大值是n-i序号+1 中介数？0 123 (00) 2 213 (10)3 231 (11) 4 312 (20) 5 321 (21)78!+27!+66!+45!+24!+33!+22!+11!2105+9104+7103+1102+9101+1100十进制数 进位制/位置计数法是一种记数方式，故亦称进位记数法/位值计数法，

15、可以用有限的数字符号代表所有的数值。可使用数字符号的数目称为基数(radix)或底数，基数为n，即可称n进位制，简称n进制。现在最常用的是十进制，还有二进制，十六进制，八进制，甚至是七进制。 进制中的基数一定是固定大小的吗？递增进位制数递增/递减进位制数 递增进位制和递减进位制数字是指数字的进制随着数字位置的不同递增或递减。 递增进位制数4121，它的进制从右向左依次是2、3、4、5即其最高位（就是数字4那位）最大可能是4；第三高位最大可能是3；第二高位最大可能是2；最末位最大可能是1 (4121) + 1 = 420021递增进位制数递增进位制数(a9 a8 a7 a6 a5 a4 a3 a

16、2 )为：a9*8! + a8*7! + .+ a3*2! + a2*1! = 序号= a9*8) + a8)*7 + .+ a3)*2 + a2)*1! 表示范围递增进位制数的87654321对应十进制序号362879（即9!-1） 加减法：注意进位不同72642321 = 72652011每位大于当前位的进制则进位172642321 4020 = 72633301被减数当前位不够减，则从上一位借相应本位的进制大小 9 8 7 6 5 4 3 2 9 8 7 6 5 4 3 222序号转化为递增进位制数a9*8! + a8*7! + .+ a3*2! + a2*1! = 序号将一个序号转换成

17、其递增进位制数首先需要找到一个比序号小的最大阶乘数（即1、2、6、24、120、720），对其进行整数除得到递增进位制的第一位；将除法的余数反复应用这个方法（当然，之后选择的余数是小一级的阶乘数），直到余数为0。序号100的递增进位制数就是4020，即4*4！+ 0*3！+ 2*2！+ 0*1！=100 4!1003)3132Mobile IntegerGiven an integer k we assign a direction to it by writing an arrow above it pointing to the left or to the right. Consider

18、 a permutation of 1,2,n in which each of the integers is given a direction.The integer k is called mobile if its arrow points to a smaller integer adjacent to it.Integer 1 can never be mobile since there is no integer smaller than 1. The integer n is always mobile, except in two cases:n is the first

19、 integer and its arrow points to the left.n is the last integer and its arrow points to the right.only 3, 5, and 6 are mobile.XX32Generating PermutationsThe permutation of 1 2 3 4 41 2 31 2 3 2 31 2 31 3 21 3 2 3 21 3 24444444Each permutation other than the first one is obtained from the preceding o

20、ne by switching two adjacent numbers.Move the largest number 4 between two endsWhen the end is met, the largest number 4 will be fixed for a step and the switching of the second largest number 3 makes 4 movable again.Step 0: All mobileStep 1: Choose the largest mobile integer 4Step 2: Switch 4 and 3

21、 as the arrow points to.Step i: 4 is fixed, the largest mobile integer is 3. After the switch between 3 and 2, switch the direction of the arrow above 4( 43)3334Switching MethodBegin with While there exists a mobile integer, dofind the largest mobile integer m.switch m and the adjacent integer its a

22、rrow points to.switch the direction of all integers p with pm.341.5.4邻位对换法递减进位制数法启发我们，能不能设计一种算法，下一个排列总是上一个排列某相邻两位对换得到的。递减进位制数字的换位是单向的，从右向左，逐个换位，直到最左端。邻位对换法的换位是双向的，通过保存数字的“方向性”来快速得到下一个排列。设定b2b3b4b5b6b7b8b9为我们要求的中介数。2的方向一定是向左。b2就是从2开始,背向2的方向所有比2小的数字的个数。知道了b2的值之后就可以依次推导出b3b4直到b9的值，规则如下：对于每一个大于2的数字i，如果i

23、为奇数，其方向性决定于bi-1的奇偶性，奇向右、偶向左。如果i为偶数，其方向性决定于bi-1+ bi-2的奇偶性，同样是奇向右、偶向左。当得到方向性后，bi的值就是背向i的方向直到排列边界这个区间里比i小的数字的个数。如此就能得到邻位对换法的中介数。 352的方向向左，背向2的方向中比2小的数字有1个，b2=13的方向由b2为奇可以断定向右，背向3的方向中比3小的数字有0个，b3=04的方向由b2+b3为奇可以断定向右，背向4的方向中比4小的数字有1个，b4=15的方向由b4为奇可以断定向右，背向5的方向中比5小的数字有2个，b5=26的方向由b4+b5为奇可以断定向右，背向6的方向中比6小的

24、数字有1个，b6=17的方向由b6为奇可以断定向右，背向7的方向中比7小的数字有3个，b7=38的方向由b6+b7为偶可以断定向左，背向8的方向中比8小的数字有7个，b8=79的方向由b8为奇可以断定向右，背向9的方向中比9小的数字有2个，b9=2 P= 839647521 ( ) b2 b3 b4 b5 b6 b7 b8 b910121372递减进位制数361.5.4邻位对换法已知(10121372)求排列。9：b8=7奇9向右 b9=2 向右第3个空，8：b6+b7=1+3=4偶8向左 b8=7 向左第8个空7：b6=1奇7向右， b7=3 向右第4个空6：b4+b5=1+2=3奇6向右，

25、b6=1,向右第2个空5：b4=1奇5向右， b5=2,向右第3个空4：b2+b3=1奇4向右, b4=1,向右第2个空3：b2=1奇3向右， b3=0,向右第1个空2：b2=1,向左第2个空38765921410121372371.5.4邻位对换法9：b8=7奇9向右 b9=3 向右第4个空，839647521 (10121372)(10121372) +1= (10121373) 836947521836475219 (10121378)(10121378) +1= (10121400) 8364572199：b8=0偶9向左 b9=0 向左第1个空，8：b6+b7=1+4=5奇8向右 b

26、8=0 向右第1个空7：b6=1奇7向右， b7=4 向右第5个空6：b4+b5=1+2=3奇6向右，b6=1,向右第2个空。38765921438Generating PermutationsThe permutation of 1 2 3 4 41 2 31 2 3 2 31 2 31 3 21 3 2 3 21 3 24444444Each permutation other than the first one is obtained from the preceding one by switching two adjacent numbers.Move the largest number 4 between two endsWhen the end is met, the largest number 4 will be fixed for a step and the switching of the second largest number 3 makes 4 movable again.Step 0: All mobileStep 1: Choose the largest