1、1组合数学的应用范畴组合数学的应用范畴 第一章第一章:排列与组合排列与组合 第二章第二章:递推关系与母函数递推关系与母函数 第三章第三章:容斥原理与鸽巢原理容斥原理与鸽巢原理 第四章第四章:Burnside引理与引理与Polya定理定理 第五章第五章:区组设计区组设计 第六章第六章:线性规划线性规划 第七章第七章:编码简介编码简介 第八章第八章:组合算法简介组合算法简介 2第一章：排列与组合第一章：排列与组合1.1 1.1 基本计数法则基本计数法则1.2 1.2 一一对应一一对应: :1.3 1.3 排列与组合排列与组合1.4 1.4 圆周排列圆周排列1.5 1.5 排列的生成算法排列的生成算
2、法1.6 1.6 允许重复的组合与不相邻的组允许重复的组合与不相邻的组合合1.7 1.7 组合意义的解释组合意义的解释1.8 1.8 应用举例应用举例1.9 1.9 * *StirlingStirling公式公式31.11.1基本计数法则基本计数法则1 1、加法法则、加法法则: :如果具有性质如果具有性质A A的事件有的事件有m m个，性质个，性质B B的事件有的事件有n n个，则具有性质个，则具有性质A A或或B B的事件有的事件有m+nm+n个。个。A A和和B B是性质无关的两个事件。是性质无关的两个事件。42 2、乘法法则、乘法法则: :若具有性质若具有性质A A的事件有的事件有m m
3、个，具有性质个，具有性质B B的事件的事件有有n n个，则具有个，则具有性质性质A A及及B B的事件有的事件有mnmn个个1.11.1基本计数法则基本计数法则5例例1.1 1.1 若从合肥到南京有若从合肥到南京有2 2条路可走，从南京条路可走，从南京到上海有到上海有3 3条路可走，从上海到杭州有条路可走，从上海到杭州有2 2条路可条路可走，问从合肥经南京、上海到杭州有多少路可走，问从合肥经南京、上海到杭州有多少路可走？走？1.11.1基本计数法则基本计数法则6例例1.21.2：用乘法法则解释：用乘法法则解释8 8卦及卦及6464卦。卦。 解：解：1 1、太极生两仪、太极生两仪 3 3、四象生
4、八卦、四象生八卦 000000，001001，010, 011010, 011 100 100，101101，110, 111110, 111 2 2、两仪生四象、两仪生四象 0000，0101，1010，1111；1.11.1基本计数法则基本计数法则7 例例1.31.3：长度为：长度为n n的的0,10,1符号串的数目符号串的数目? ? 例例1.4 1.4 人类人类DNADNA链的长度为链的长度为2.12.110101010, ,链上链上每一位由每一位由T,C,A,GT,C,A,G四种化合物组成四种化合物组成, ,求人类求人类DNADNA链链的可组成数目。的可组成数目。1.11.1基本计数法
5、则基本计数法则8例例1.51.5：求布尔函数：求布尔函数f(xf(x1 1,x,x2 2,x,xn n) )的数目的数目以以n=2n=2为例：为例：f(xf(x1 1,x,x2 2) )有四种方式：有四种方式：f(0,0),f(0,1),f(1,0),f(1,1)f(0,0),f(0,1),f(1,0),f(1,1)。1 1、f(0,0)=0,f(0,1)=0,f(1,0)=0,f(1,1)=0f(0,0)=0,f(0,1)=0,f(1,0)=0,f(1,1)=0。2 2、f(0,0)=0,f(0,1)=0,f(1,0)=0,f(1,1)=1f(0,0)=0,f(0,1)=0,f(1,0)=0
6、,f(1,1)=1。对应着长度为对应着长度为2 22 2的字符串，每一位都可以取的字符串，每一位都可以取0 0或或1;1;乘法：乘法：2 2 2 22 2自变量数为自变量数为n n个时：个时：2 2 2 2n n1.11.1基本计数法则基本计数法则*9 1 1、从、从n n个数中找出最大值问题个数中找出最大值问题 2 2、n n个人参加单淘汰赛，最后产生冠军的个人参加单淘汰赛，最后产生冠军的过程。过程。1.2 1.2 一一对应一一对应10例例1.61.6：求：求n n2 2个人站成一排和站成个人站成一排和站成n n排（方阵）排（方阵）的方案数，并比较两种方案数的大小？的方案数，并比较两种方案数
7、的大小？ 解：解：9 9个人站成一排的方案数是个人站成一排的方案数是9!9!，设设a a1 1a a2 2a a3 3a a4 4a a5 5a a6 6a a7 7a a8 8a a9 9是是9 9个人的一排，个人的一排，可构成一个方阵可构成一个方阵a a1 1a a2 2a a3 3a a4 4a a5 5a a6 6a a7 7a a8 8a a9 9给定一个方阵给定一个方阵b b1 1b b2 2b b3 3b b4 4b b5 5b b6 6b b7 7b b8 8b b9 9也唯一确定一排也唯一确定一排b b1 1b b2 2b b3 3b b4 4b b5 5b b6 6b b7
8、 7b b8 8b b9 9因此这两种站位方式的方案数一样多，都是因此这两种站位方式的方案数一样多，都是9!9!1.2 1.2 一一对应一一对应11例例1.61.6：求：求n n2 2个人站成一排和站成个人站成一排和站成n n排（方阵）排（方阵）的方案数，并比较两种方案数的大小？的方案数，并比较两种方案数的大小？9 9个人站成方阵的方案数为：个人站成方阵的方案数为：C(9,3)3!C(6,3)3!C(3,3)3!C(9,3)3!C(6,3)3!C(3,3)3! 9! 3! 3! 3 ! 3! 6! 3! 3 ! 6! 91.2 1.2 一一对应一一对应12 定理定理1.1 n1.1 n个有标号
9、个有标号1,2,n1,2,n的顶点的树的顶点的树的数目等于的数目等于n nn-2n-2。（。（n=2n=2）12534 设一棵树的顶点集为设一棵树的顶点集为A A 1 1、从中找到编号最小的、从中找到编号最小的叶子结点，去掉该叶子结点叶子结点，去掉该叶子结点a a1 1及其邻接边及其邻接边(a(a1 1,b,b1 1) )。 2 2、重复以上过程。只到、重复以上过程。只到剩一条边为止。剩一条边为止。 (1,2),(4,3),(3,2) (1,2),(4,3),(3,2) 这棵树对应序列（这棵树对应序列（2 2，3 3，2 2） 一个棵对应序列一个棵对应序列B=bB=b1 1b b2 2b b3
10、 3bbn-2n-2而且是唯一的而且是唯一的1.2 1.2 一一对应一一对应1312534 树的顶点集合为树的顶点集合为12345 12345 这棵树对应序列（这棵树对应序列（2 2，3 3，2 2） 任给一个序列任给一个序列BbBb1 1,b,b2 2,b,b3 3,b,bn-2n-2 1 1、从、从A A找到最小的不属于找到最小的不属于B B的元素的元素, ,设为设为a a1 1, ,与与b b1 1连连接，从接，从A A中去掉中去掉a a1 1，从，从B B中去掉中去掉b b1 1. . 2 2、重复以上过程只到、重复以上过程只到B B为空，为空，A A中剩余两个中剩余两个 3 3、连接
11、剩余的两个顶点。、连接剩余的两个顶点。1.2 1.2 一一对应一一对应*141.31.3：排列与组合：排列与组合 1 1、排列的定义：设、排列的定义：设A=aA=a1 1,a,a2 2,a,an n 是是n n个不个不同的元素的集合，任取同的元素的集合，任取A A中中r r个元素按顺序排成一个元素按顺序排成一列，称为从列，称为从A A中取中取r r个的一个排列，个的一个排列，r r满足满足0rn0rn。 从从n n个不同的球中取一个球放在第一个盒子中，个不同的球中取一个球放在第一个盒子中， 从余下的从余下的n-1n-1个球中取一个球放在第二个盒子中，个球中取一个球放在第二个盒子中， 从余下的从
12、余下的n-(r-1)n-(r-1)个球中取一个放在第个球中取一个放在第r r个盒子中。个盒子中。(1)(1)(2)(2)(3)(3)( () )(r)(r) 根据乘法法则：根据乘法法则： P(n,r)=n(n-1)(n-r+1)=n!P(n,r)=n(n-1)(n-r+1)=n!(n-r)!(n-r)!15全排列全排列:P(n,n)=n(n-1)2:P(n,n)=n(n-1)21=n!1=n!1.31.3：排列与组合：排列与组合2 2、组合的定义：当从、组合的定义：当从n n个不同元素中取出个不同元素中取出r r个个而不考虑它的顺序时而不考虑它的顺序时, ,称为从称为从n n中取中取r r个的
13、组合个的组合, ,其数目记为其数目记为C(n,r)C(n,r)。公式：从公式：从n n中取中取r r的组合数记作的组合数记作C(n,r) C(n,r) 从从n n中取中取r r的排列数是的排列数是P(n,r)P(n,r)。C(n,r)=P(n,r)/r!C(n,r)=P(n,r)/r! =n!/r!(n-r)!=n!/r!(n-r)!二者之间的关系二者之间的关系: :16第一章：排列与组合第一章：排列与组合 排列可以看作排列可以看作n n个不同的元素放进个不同的元素放进r r个个不同的盒子的放法不同的盒子的放法. . 组合可以看作组合可以看作n n个不同的元素放进个不同的元素放进r r个个相同
14、的盒子的放法相同的盒子的放法. .公式公式1 1：C(n,r)=C(n,n-r)C(n,r)=C(n,n-r)17 从从5 5个元素中取个元素中取3 3个进行排列的算法：个进行排列的算法： int a5=1,2,3,4,5,b3int a5=1,2,3,4,5,b3； for(i=0;i5;i+)for(i=0;i5;i+) b0=ai; b0=ai; for(j=0;j5;j+) for(j=0;j5;j+) if (j=i) j+; if (j=i) j+; else b1=aj; else b1=aj; for(k=0;k5;k+) for(k=0;k5;k+) if(k=i|k=j)
15、k+; if(k=i|k=j) k+; else b2=ak; else b2=ak; 打印打印bb1.31.3：排列与组合：排列与组合18 例例1.7:1.7:由由5 5种颜色的星状物种颜色的星状物,20,20种不同的花共种不同的花共2525个元素中任取个元素中任取5 5个排成如下图案：两边是星状物个排成如下图案：两边是星状物, ,中中间是间是3 3朵花，问共有多少种这样的图案？朵花，问共有多少种这样的图案？ 解解1 1：5 52020191918184=136800 4=136800 2020种不同的花取种不同的花取3 3种排列的排列数为：种排列的排列数为：P(20,3)=20!/17!=
16、20P(20,3)=20!/17!=20* *1919* *18=684018=6840根据乘法法则，共有图案数为：根据乘法法则，共有图案数为：68406840* *20=13680020=136800解解2 2：5 5种颜色的星状物取两个排列的排列数为种颜色的星状物取两个排列的排列数为 P(5,2)=5!/3!=5P(5,2)=5!/3!=5* *4=20 4=20 1.31.3：排列与组合：排列与组合19 1.8 1.8 随机地选择随机地选择n n个人，求个人，求n n个人至少有两人生个人至少有两人生日相同的概率日相同的概率( (不考虑润年不考虑润年) ) 解解: : n n个人生日不同的
17、方案数是个人生日不同的方案数是: : 365 365* *364364* * *(365-n+1)=P(365,n)(365-n+1)=P(365,n) n n个人生日的总方案数是个人生日的总方案数是: : 365 365n n 至少有两人生日相同的概率至少有两人生日相同的概率: : 1-P(365,n)/365 1-P(365,n)/365n n1.31.3：排列与组合：排列与组合*201.41.4：圆周排列：圆周排列 定义：在排列中，如果我们不横排而是定义：在排列中，如果我们不横排而是将各元素排列在一个圆周上，那么我们称这种将各元素排列在一个圆周上，那么我们称这种排列方式为圆周排列。排列方
18、式为圆周排列。 在排列中在排列中1234,2341,3412,41231234,2341,3412,4123为四个不为四个不同的排列，而在圆排列中这些排列是一个同的排列，而在圆排列中这些排列是一个. . 规定相对位置不变算一个排列。规定相对位置不变算一个排列。21将从将从n n中取中取r r个作圆排列的排列数记作个作圆排列的排列数记作Q(n,r)Q(n,r)。从从n n中取中取r r个作排列，与圆排列相比，重复了个作排列，与圆排列相比，重复了r r倍；倍；公式：公式：Q(n,r)=P(n,r)/rQ(n,r)=P(n,r)/r，Q(n,n)=P(n,n)/n=n!/n=(n-1)!Q(n,n)
19、=P(n,n)/n=n!/n=(n-1)!1.41.4：圆周排列：圆周排列Q(n,r)=P(n,r)/r=n!/r(n-r)!Q(n,r)=P(n,r)/r=n!/r(n-r)!22 例例1.191.19：5 5颗不同的红色珠子，颗不同的红色珠子，3 3颗不同的蓝颗不同的蓝色珠子装在圆板的四周色珠子装在圆板的四周, ,试问有多少种方案？若蓝试问有多少种方案？若蓝色珠子不相邻又有多少种排列方案？蓝色珠子在色珠子不相邻又有多少种排列方案？蓝色珠子在一起又如何？一起又如何？ 解：解：(1)Q(8,8)=P(8,8)/8=7!(1)Q(8,8)=P(8,8)/8=7!。 (3) (3)蓝色珠子在一起蓝
20、色珠子在一起 Q(6,6)3!=5!3!Q(6,6)3!=5!3!。 (2) (2) 蓝色珠子不在一起。蓝色珠子不在一起。 首先首先5 5颗不同的红色珠子作圆排列，共有颗不同的红色珠子作圆排列，共有 Q(5,5)=4!Q(5,5)=4!， 3 3颗不同的蓝色珠子排在红色珠子中间颗不同的蓝色珠子排在红色珠子中间 4! 4!5 54 43 31.41.4：圆周排列：圆周排列*23 例例1.201.20：5 5对夫妇出席一宴会，围一圆桌对夫妇出席一宴会，围一圆桌而坐，试问有几种不同的方案？若要求每对而坐，试问有几种不同的方案？若要求每对夫妻相邻又有多少种方案夫妻相邻又有多少种方案? ? 解：解： 1
21、 1）座位无限制）座位无限制 Q(10,10)=P(10,10)/10=10!/10=9!=362880Q(10,10)=P(10,10)/10=10!/10=9!=362880 共有共有362880362880种方式。种方式。 2 2）夫妇相邻而坐）夫妇相邻而坐 首先可以将一对夫妇作为一个元素来看待，首先可以将一对夫妇作为一个元素来看待，共有共有Q(5,5)=P(5,5)/5=24Q(5,5)=P(5,5)/5=24。 但夫妇可以交换坐位，但夫妇可以交换坐位，5 5对夫妇共有对夫妇共有2 25 5种方式。种方式。 根据乘法法则：若夫妻相邻而坐，共根据乘法法则：若夫妻相邻而坐，共有有 2424
22、2 25 5=24=2432=76832=768种方式。种方式。 1.41.4：圆周排列：圆周排列*24第一章：排列与组合第一章：排列与组合 多重集的排列多重集的排列 设设S S是一个多重集，有是一个多重集，有K K个不同类型的元素，个不同类型的元素，各元素的重复分别为各元素的重复分别为n n1 1,n,n2 2,n,nk k,n=n,n=n1 1+n+n2 2+n+nk k, ,则则S S的排列数为的排列数为: :!.!21knnnn25第一章：排列与组合第一章：排列与组合 证明：给定多重集证明：给定多重集S S，有，有k k种类型的元素，比种类型的元素，比如说如说a a1 1,a,a2 2
23、,a,a3 3,a,ak k, ,且分别有重数且分别有重数n n1 1,n,n2 2,n,nk k, ,元素的总个数元素的总个数n=nn=n1 1+n+n2 2+n+nk k, , 现在存在现在存在n n个位置个位置, ,我们要在我们要在n n个位置放个位置放S S的一的一个元素个元素, ,首先要确定哪些位置放首先要确定哪些位置放a a1 1的元素的元素, ,共共有有1nnC 剩下剩下n-nn-n1 1个位置个位置, a, a2 2的元素的元素, ,共有共有21nnnC. 剩下剩下n-nn-n1 1- -n-nk-1k-1个位置个位置, a, ak k的元素的元素, ,共有共有kknnnnC1
24、1.26第一章：排列与组合第一章：排列与组合 根据剩法法则根据剩法法则: : S S的排列的总数的排列的总数kknnnnnnnnnnnnnCCCC11321211.!)!()!(!)!()!(!)!(!332121221111nnnnnnnnnnnnnnnnnn!)!()!.(21121kkknnnnnnnnn!.!21knnnn27练习题练习题 1 1、求、求10104040和和20203030的公因数的数的公因数的数目。目。 解：解：10104040=2=240405 54040，20203030=2=260605 53030C(41,1)C(41,1)* *C(31,1)C(31,1)2
25、82 2、试证、试证n n2 2的整除数的数目是奇数。的整除数的数目是奇数。mamaapppn.2121mamaapppn222212.21) 1 , 12(.) 1 , 12() 1 , 12(21maCaCaC练习题练习题29 1.13 1.13、有、有n n个不同的整数，从中取出两组来，个不同的整数，从中取出两组来，要求第要求第1 1组的最小数大于另一组的最大数。组的最小数大于另一组的最大数。设取的第一组数有设取的第一组数有a a个个, ,第二组有第二组有b b个个, ,要求第一组数中最小数大于第二组中最大的，要求第一组数中最小数大于第二组中最大的，即只要取出一组即只要取出一组m m个数
26、个数( (设设m=a+b),m=a+b),从大到小从大到小取取a a个作为第一组个作为第一组, ,剩余的为第二组。剩余的为第二组。此时方案数为此时方案数为C(n,m)C(n,m)。从从m m个数中取第一组数共有个数中取第一组数共有m-1m-1中取法。中取法。(m-1)C(n,m)(m-1)C(n,m)练习题练习题30nmnnmnCm2112),() 1(练习题练习题31第一章：排列与组合第一章：排列与组合1.1 1.1 基本计数法则基本计数法则1.2 1.2 一一对应一一对应: :1.3 1.3 排列与组合排列与组合1.4 1.4 圆周排列圆周排列1.5 1.5 排列的生成算法排列的生成算法1
27、.6 1.6 允许重复的组合与不相邻的组允许重复的组合与不相邻的组合合1.7 1.7 组合意义的解释组合意义的解释1.8 1.8 应用举例应用举例1.9 1.9 * *StirlingStirling公式公式321.5 1.5 排列的生成算法：排列的生成算法： 排列的生成算法排列的生成算法: : 对于给定的字符集，用有效的方法将对于给定的字符集，用有效的方法将所有可能的排列无重复无遗漏地枚举出来。所有可能的排列无重复无遗漏地枚举出来。8 8（a a1111）1 1 （a a1212）6 6 （a a1313）3 3 （a a2121）5 5 （a a2222）7 7 （a a2323）4 4
28、（a a3131）9 9 （a a3232）2 2 （a a3333）3 3阶幻方阶幻方九宫图九宫图21)(NNS22N总和为21)N(NH2N幻方值33 从从5 5个元素中取个元素中取3 3个进行排列的算法：个进行排列的算法： int a5=1,2,3,4,5,b3int a5=1,2,3,4,5,b3； for(i=0;i5;i+)for(i=0;i5;i+) b0=ai; b0=ai; for(j=0;j5;j+) for(j=0;j5;j+) if (j=i) continue; if (j=i) continue; else b1=aj; else b1=aj; for(k=0;k5
29、;k+) for(k=0;k5;k+) if(k=i|k=j) continue; if(k=i|k=j) continue; else b2=ak; else b2=ak; 打印打印bb1.31.3：排列与组合：排列与组合34n n个元素的全排列有个元素的全排列有n!n!个个, ,从从0 0到到n!-1n!-1共共n!n!个数。个数。序数法的思想：序数法的思想：n n个元素的全排列与个元素的全排列与n!n!个数一一对应。个数一一对应。序数法找到了一种序数法找到了一种n!n!个数直接计算出个数直接计算出n!n!个排列的个排列的算法：算法：1 1、0 0到到n!-1n!-1这这n!n!个数与如下
30、序列一一对应：个数与如下序列一一对应：（a an-1n-1，a an-2n-2，aa1 1） 0 0 a ai i i i；2 2、从每一个这样的序列我们可以生成一个排列。、从每一个这样的序列我们可以生成一个排列。 一、序数法一、序数法 35公式：公式：n!-1=(n-1)(n-1)!+(n-2)(n-2)!+2n!-1=(n-1)(n-1)!+(n-2)(n-2)!+22!+ 2!+ 1 11!1!等同于：等同于：n!=(n-1)(n-1)!+(n-2)(n-2)!+2n!=(n-1)(n-1)!+(n-2)(n-2)!+22!+ 2!+ 1 11!+11!+1一般一般: (k-1): (k
31、-1)(k-1)!+(k-1)!=k!(k-1)!+(k-1)!=k! (n-2)(n-2)!+(n- (n-2)(n-2)!+(n-2)!=(n-1)!2)!=(n-1)! (n-1)(n-1)!+(n-1)!=n! (n-1)(n-1)!+(n-1)!=n! 一、序数法一、序数法 36 定理定理3 3：令：令n n 0,00,0m mn!-1n!-1，则，则m m可以可以唯一唯一地表地表示为：示为：m=am=an-1n-1(n-1)!+a(n-1)!+an-2n-2(n-2)!+a(n-2)!+a1 1 1!1! 其中：其中：0 0 a ai i i, i=1, 2, , n-1i, i=
32、1, 2, , n-1。（一）。（一） a ai i由由m m唯一确定。唯一确定。 （二）（二） 反过来，任何满足上式的数反过来，任何满足上式的数m m都是一个大于或都是一个大于或等于等于0 0，小于或等于，小于或等于n!-1n!-1的数。的数。 （三）（三） 最大值是：最大值是：最小值是：最小值是：0 0(n-1)!+0(n-1)!+0(n-2)!+ 0(n-2)!+ 01!=01!=0 因此：（三）成立因此：（三）成立(n-1)(n-1)!+(n-2)(n-2)!+2(n-1)(n-1)!+(n-2)(n-2)!+22!+ 2!+ 1 11!=n!-11!=n!-1 一、序数法一、序数法
33、37 证明：（二）唯一表示性证明：（二）唯一表示性 设设m=m=a an-1n-1(n-1)!+a(n-1)!+an-2n-2(n-2)!+a(n-2)!+a1 1 1!1! m=b m=bn-1n-1(n-1)!+b(n-1)!+bn-2n-2(n-2)!+b(n-2)!+b1 1 1!1! 显然显然a a1 1=b=b1 1, ,如果一直到如果一直到a an-1 n-1 = =b bn-1n-1，定理得证：定理得证： 否则令否则令k k=mini,a=mini,ai ibbi i , ,那么那么: : a ai i=b=bi i , ,当当ikik时时如果两边同时除以如果两边同时除以(k+
34、1)!(k+1)! 我们可以看到等式左边余数为我们可以看到等式左边余数为a ak kk!k!等式右边余数为等式右边余数为b bk kk k! !由由a ak kb bk k, ,与假设予盾，因此表示法是唯一的。与假设予盾，因此表示法是唯一的。11!nkiinkiiibia 一、序数法一、序数法 38 证明：（一）可表示证明：（一）可表示性性 怎样求序列怎样求序列 a an-1n-1, a, an-2n-2, , a a1 1 m=am=an-1n-1(n-1)!+a(n-1)!+an-2n-2(n-2)!+a(n-2)!+a2 2 2!2!+ + a a1 1 1!1!数数m m除以除以2 2
35、的整数部分与余数是什么？的整数部分与余数是什么？整数部分是：整数部分是：a an-1n-1(n-1)!/2+ +a(n-1)!/2+ +a3 3 3!/2 +a3!/2 +a2 2余数是余数是a a1 1 如果用如果用m m除以除以2 2的整数部分再除以的整数部分再除以3 3，余数就，余数就是是a a2 2, ,其它项以此类推。其它项以此类推。 一、序数法一、序数法 39例例 1: 1: 将将m=4000m=4000展开。展开。40007!=504040007!=5040解：解： b=4000, b=4000, a1=b%2=0; b=b/2=2000;a1=b%2=0; b=b/2=2000
36、;a2=b%3=2; b=b/3=666;a2=b%3=2; b=b/3=666; a3=b%4=2; b=b/4=166; a3=b%4=2; b=b/4=166; a4=b%5=1; b=b/5=33;a4=b%5=1; b=b/5=33; a5=b%6=3; b=b/6=5;a5=b%6=3; b=b/6=5; a6=b%7=5; b=b/7=0;a6=b%7=5; b=b/7=0;4000=54000=5* *6!+36!+3* *5!+15!+1* *4!+24!+2* *3!+23!+2* *2! +02! +0* *1!1!400040005,3,1,2,2,5,3,1,2,2,
37、00 一、序数法一、序数法 40int a=0;int a=0;int m,n;/ 0=m=n!-1int m,n;/ 0=m=n!-1int b=mint b=m；i int index =nt index =1 1; ; do do aindex=aindex=b b% %( (indexindex+1)+1); ; b b = = b b/ /( (indexindex+1)+1); ; index+;index+; while( while(b b); ); 推论推论 从从0 0到到n!-1n!-1的的n!n!个整数与序列个整数与序列 a an-1n-1, a, an-2n-2, ,
38、a a1 1 一一对应。这里一一对应。这里 0 0 a a1 1 1,01,0 a a2 2 2, , 02, , 0 a an-1n-1 n-1n-1算法算法: : 一、序数法一、序数法 41例例2:2:对于对于0 0 m m 23=4!-123=4!-1,m,m可以展开为：可以展开为： m=am=a3 3 3!+a3!+a2 2 2!+a 2!+a1 1 1! 1!。 求所有的序列求所有的序列aa3 3, a, a2 2,a,a1 1 ；解：解： 0 0000, 1000, 1001, 2001, 2010, 3010, 3011, 011, 4 4020, 5020, 5021, 602
39、1, 6100, 7100, 7101, 101, 8 8110, 9110, 9111, 10111, 10120, 11120, 11121, 121, 12 12101, 13101, 13201, 14201, 14210, 15210, 15211211 16 16220, 17220, 17221, 18221, 18300, 19300, 19301, 301, 20 20301, 21301, 21311, 22311, 22320, 23320, 23321321 一、序数法一、序数法 42怎样建立怎样建立a(3)a(2)a(1)a(3)a(2)a(1)p(1)p(2)p(3
40、)p(4)p(1)p(2)p(3)p(4)a(3)a(3) 确定确定4 4的位置的位置, ,a(2)a(2)确定确定3 3的位置的位置a(1)a(1)确定确定2 2的位置的位置, ,剩余的位置就是剩余的位置就是1 1的位的位置置 例例3 3:021,3 32 21 14 4 一、序数法一、序数法 例例3 3: 201201,432143求求n n个不同的数的全排列，主要有以下两步：个不同的数的全排列，主要有以下两步：1 1、求出、求出0 0到到n!-1n!-1之间各数对应的序列之间各数对应的序列 a an-1n-1, a, an-2n-2, , a a1 1 m=a m=an-1n-1(n-1
41、)!+a(n-1)!+an-2n-2(n-2)!+a(n-2)!+a2 2 * * 2!+a2!+a1 1* *1!1!2 2、由、由 a an-1n-1, a, an-2n-2, a, a1 1 确定排列序列确定排列序列p p1 1p p2 2ppn n a an-1n-1, ,确定确定n n的位置，的位置， a an-2n-2确定确定n-1n-1的位置，的位置， a a1 1确定确定2 2的位置，的位置， 剩下的是剩下的是1 1的位置。的位置。 一、序数法一、序数法 44int int resultresult 1717 = 0 ; = 0 ; /记录排序记录排序int aint a171
42、7 = 0 ; = 0 ; /记录序列记录序列void permute( intvoid permute( int n) n) int fact = 1,i; int fact = 1,i; for( i = 1; i = n; i+ ) for( i = 1; i = n; i+ ) fact fact * *= i;/= i;/求求n n的阶乘的阶乘1 1、求阶乘、求阶乘 一、序数法一、序数法 THANK YOUSUCCESS2022-5-1946for( i = 0; i fact; i+ ) for( i = 0; i 0;j-)for(j=n-1;j0;j-)index=n;inde
43、x=n; int spacecount=0; int spacecount=0; while(ajwhile(aj spacecount|rspacecount|re es sultultindex!=0)index!=0) if( rif( resultesultindex=0)index=0) spacecount+; spacecount+; index-;index-; r re es sulultindex=j+1;tindex=j+1; 3 3、ajaj确定确定j+1j+1的位置的位置 一、序数法一、序数法 48/最后一个位置是最后一个位置是1 1的位置的位置 index = n;
44、 index = n; while( r while( resultesultindex!= 0)index!= 0) index-; index-; r resultesult index = 1; index = 1; / / 输出结果输出结果 for( j = 1; j for( j = 1; j = = n; j+ ) n; j+ ) cout r cout re es sulult j endl;t j endl; r re es sulult j = 0;t j = 0; 一、序数法一、序数法 49void main()void main() int n; int n;cout c
45、out n;cin n;permute(n);permute(n); 一、序数法一、序数法 *50字典序法的思想：字典序法的思想： 对于对于n n个字符的任何二个排列，我们都可以个字符的任何二个排列，我们都可以比较它的大小。比较它的大小。 1 1、初始排列我们可以给出来，、初始排列我们可以给出来， 1,2,3,n-1,n1,2,3,n-1,n二、字典序法二、字典序法 2 2、设计算法找到比上一个排序大的排列中最、设计算法找到比上一个排序大的排列中最小的一个。小的一个。 1,2,3,n,n-11,2,3,n,n-1 3 3、重复以上过程直到最大。、重复以上过程直到最大。 n,n-1,3,2,1n
46、,n-1,3,2,151 例例4 4：求：求839647521839647521的下一个排列。的下一个排列。 此时此时5 5右边为右边为74217421，倒置为，倒置为12471247，即得下，即得下一个排列一个排列:839651247:839651247。 只要后边的大数与前面的小数交换，都只要后边的大数与前面的小数交换，都比原数大，那个是最小的一个。比原数大，那个是最小的一个。 这一个与下一个有尽可能长的共同前缀，这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。也即变化限制在尽可能短的后缀上。 找到前面数小于后边数的最后一个，找到前面数小于后边数的最后一个，4 4 4
47、4与后面比它大最接近他的数交换，与后面比它大最接近他的数交换，5 5二、字典序法二、字典序法52 例例4 4：求：求839647521839647521的下一个排列。的下一个排列。 1 1：从排列的末尾开始：从排列的末尾开始, ,逐步向前搜索逐步向前搜索, ,直到找到直到找到比其后面相邻的数小的数比其后面相邻的数小的数: :如果未找到如果未找到, ,表明不再有下一个排列表明不再有下一个排列, ,程序终止程序终止; ;2 2：从该数后面的序列中寻找比该数大的最小的：从该数后面的序列中寻找比该数大的最小的数来替换它数来替换它( (使用交换使用交换););3 3：将余下的数反转。：将余下的数反转。二
48、、字典序法二、字典序法53 1 1、求满足关系式、求满足关系式p pj jppj+1j+1的下标的下标j j的最大值，的最大值，设为设为i , i=maxji , i=maxjp pj jppj+1j+1 例如：例如： 839647521839647521中中i=5 i=5 注注: :该该位置值为位置值为4 4 2 2、求出、求出i i后，再求满足关系式后，再求满足关系式p pi ippk k的的k k的最的最大值，设为大值，设为h, h=maxkh, h=maxkp pi ippk k 例如：例如： 839647521839647521中中h=7 h=7 注注: :该位置值该位置值为为5 5
49、 3 3、 p pi i与与p ph h 互换。得新排列互换。得新排列P P1 1P P2 2PPi-i-1 1P Pi iP Pi+1i+1PPn n 例如：例如： 839647521839647521换成换成839657421839657421 4 4、 将新排列将新排列P P1 1P P2 2PPi-1i-1P Pi iP Pi+1i+1PPn n中的中的P Pi+1i+1PPn n顺序逆转，得到顺序逆转，得到P P1 1P P2 2PPi iP Pn n P Pi+1i+1 二、字典序法二、字典序法54 void main ()void main ()int i,j,k,int i,j
50、,k,h,h,t,n,p100,select;t,n,p100,select; select=1; / select=1; /* *selectselect用于控制是否循环执行程序用于控制是否循环执行程序* */ / while (select) while (select) printf(“please input an Integer n:”); printf(“please input an Integer n:”); scanf(%d,&n);scanf(%d,&n); printf(n); printf(n); printf(“please input %d number print
