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

全排列的生成算法对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。

字典序法按照字典序求下一个排列的算法 /*例字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。

注意一个全排列可看做一个字符串，字符串可有前缀、后缀。

*/生成给定全排列的下一个排列所谓一个全排列的下一个排列就是这一个排列与下一个排列之间没有其他的排列。

这就要求这一个排列与下一个排列有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。

/*例 839647521是1—9的排列。

1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。

否则找出第一次出现下降的位置。

算法: 由P1P2…Pn 生成的下一个排列的算法如下:1. 求i=max{j| Pj-1<Pj}2. 求l=max{k| Pi-1<Pk }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代码，修改一下和自己的程序兼容就行了，也不看是怎么来的，不是我不想看，实在是说的很抽象，那一大堆公式来吓人，一个实例都不给，更有甚者连算法都没有，只是在那里说，想看都看不懂，也没那个耐心取理解那些人写出来的那种让人无法忍受的解释。

第1章 排列与组合1.1 从{1,2,…,50}中找一双数{a,b}，使其满足：()5;() 5.a ab b a b -=-≤[解] (a) 5=-b a将上式分解，得到55a b a b -=+⎧⎨-=-⎩a =b –5，a=1，2，…，45时，b ＝6，7，…，50。

满足a=b-5的点共50-5=45个点. a = b+5，a=5，6，…，50时，b ＝0，1，2，…，45。

满足a=b+5的点共45个点. 所以，共计2×45=90个点. (b) 5≤-b a(610)511(454)1651141531+⨯+⨯-=⨯+⨯=个点。

1.2 5个女生，7个男生进行排列，(a) 若女生在一起有多少种不同的排列？ (b) 女生两两不相邻有多少种不同的排列？(c) 两男生A 和B 之间正好有3个女生的排列是多少？[解] (a) 女生在一起当作一个人，先排列，然后将女生重新排列。

（7＋1）!×5!=8!×5!＝40320×120=4838400(b) 先将男生排列有7!种方案，共有8个空隙，将5个女生插入，故需从8个空中选5个空隙，有58C 种选择。

将女生插入，有5!种方案。

故按乘法原理，有：7!×58C ×5!=33868800(种)方案。

(c) 先从5个女生中选3个女生放入A ，B 之间，有35C 种方案，在让3个女生排列，有3!种排列，将这5个人看作一个人，再与其余7个人一块排列，有(7+1)! = 8!由于A ，B 可交换，如图**A***B** 或 **B***A**故按乘法原理，有：2×35C ×3!×8!=4838400（种）1.3 m 个男生，n 个女生，排成一行，其中m ，n 都是正整数，若(a) 男生不相邻(m ≤n+1)； (b) n 个女生形成一个整体； (c) 男生A 和女生B 排在一起； 分别讨论有多少种方案.[解] (a) 先将n 个女生排列，有n!种方法，共有n+1个空隙，选出m 个空隙，共有mn C 1+种方法，再插入男生，有m!种方法，按乘法原理，有：n!×mn C 1+×m!＝n!×)!1(!)!1(m n m n -++×m!=)!1()!1(!m n n n -++种方案。

组合数学全排列生成算法组合数学中的全排列深成算法历来是组合数学考试的重要考察点，因此在这里我简单的介绍一下6种全排列生成算法的详细过程，并借此比较它们之间的优劣之处。

不论是哪种全排列生成算法，都遵循着“原排列”→“原中介数”→“新中介数”→“新排列”的过程。

其中中介数依据算法的不同会的到递增进位制数和递减进位制数。

关于排列和中介数的一一对应性的证明我们不做讨论，这里仅仅给出了排列和中介数的详细映射方法。

相信熟练掌握了方法就可以顺利通过这部分的考察。

递增进位制和递减进位制数所谓递增进位制和递减进位制数字是指数字的进制随着数字位置的不同递增或递减。

通常我们见到的都是固定进制数字，如2进制，10进制等。

m位n进制数可以表示的数字是m*n个。

而m位递增或递减进位制数则可以表示数字m!个。

例如递增进位制数4121，它的进制从右向左依次是2、3、4、5。

即其最高位（就是数字4那位）最大值可能是4；第三高位最大可能是3；第二高位最大可能是2；最末位最大可能是1。

如果将4121加上1的话，会使最末位得到0，同时进位；第二位的2与进位相加，也会得到0，同时进位；第三位的1与进位相加得到2，不再进位。

最终得到结果是4200。

递减进位制的道理是一样的，只不过进制从右向左依次是9、8、7、6……，正好与递增进位制相反。

很明显，递减进位制的一个最大的好处就是加法不易进位，因为它在进行加法最频繁的末几位里（最右边）进制比较大。

接下来要了解的是递增进位制、递减进位制数和其序号的关系。

递增、递减进位制数可以被看作一个有序的数字集合。

如果规定递增进位制和递减进位制数的0的序号是十进制0，递增进位制数的987654321和递减进位制数的123456789对应十进制序号362880（即9!），则可以整理一套对应法则。

其中，递增进位制数（a1 a2 a3 a4 a5 a6 a7 a8 a9）为：a1*9! + a2*8! + ….+ a8*2! + a9*1! =序号例如序号100的递增进位制数就是4020，即4*4！+ 0*3！+ 2*2！+ 0*1！=100。

《组合数学》第二讲排列组合生成算法1一. 排列生成算法z排列生成有几种典型算法, 这些算法都很有成效. 它们在实际中具有广泛应用价值.1.序数法2.字典序法3.邻位互换法(Johnson-Trotter)4.轮转法31. 序数法z序数法基于一一对应概念.z先在排列和一种特殊的序列之间建立一种一一对应关系, 然后再给出由序列产生排列的方法z因为序列的产生非常方便, 这样我们就可以得到一种利用序列来生成排列的方法.z如何建立这种一一对应?45z 思路类似数的10进制、2进制和p 进制表示.;90,1010≤≤=∑−=k m k k k a a n;10,210≤≤=∑−=k m k k k a a n.10,1−≤≤=∑−=p a p a n k m k kkz这相当于自然数与某种序列之间建立了一一对应关系.z可以利用置换来表示整数:n!=n(n-1)! =(n-1+1)(n-1)!= (n-1)(n-1)!+(n-1)!(n-1)!= (n-2)(n-2)!+(n-2)!n!= (n-1)(n-1)!+ (n-2)(n-2)!+ (n-3)(n-3)!+…+2•2!+1•1!+16z n!-1=(n-1) (n-1)!+(n-2) (n-2)!+(n-3) (n-3)!+ …+2•2!+1•1!z可以证明, 从0到n!-1之间的任何整数m 都可唯一地表示为:m=a n-1 (n-1)!+a n-2 (n-2)!+…+a2•2!+a1•1!其中0≤a≤i, i=1,2, …,n-1.iz m与序列(a n-1,a n-2 ,…a2,a1)一一对应z书中有确定这些系数的方法.z例如：10＝1⋅3!＋2⋅2!＋0⋅1!7z因为满足条件0≤a≤i, 1≤i≤n-1 （2.1）i的序列(a, a n-2, …, a2, a1)n-1共有n!个, 这恰好与0到n!-1的n!个整数一一对应.z需要建立满足条件(2.1)的n!个序列(a, a n-2, …, a2, a1)和n元集合S的n-1全部排列之间的一一对应关系.89z 还需要给出一种办法, 由每个满足条件(2.1)的序列(a n -1,a n -2, …,a 2,a 1)可生成唯一的一个排列.z 这样我们就可以产生出所有的排列. z 怎么样由一个满足条件(2.1)的序列产生一个n 阶排列?z 如何把1,2,…,n 的一个排列与一个满足条件(2.1)的序列建立起直接的关系?10z 行列式定义中有逆序数的概念, 就是一个排列中违反自然顺序的数对: 比如12354的逆序数为1, 而43215的逆序数为6.z 设p 1p 2…p n 是任意一个n 元排列, 则i +1后面比i +1小的数字的个数a i 总不超过i , 即a i ≤i , i =1,2,…,n -1.z 这样自然由一个排列得到一个序列(a n -1,a n -2,…,a 2,a 1), 而且满足条件(2.1).11z 我们可以如下建立序列与排列的对应:z 设序列(a n -1,a n -2, …,a 2,a 1)满足条件(2.1).则它所对应的排列为(p)=p 1p 2…p n , 其中a i 可以看作是排列(p)中数i +1所在位置后面比i +1小的数的个数.z 要说明这种对应的合理性, 必须清楚. 如何由序列产生出它所对应的排列.z 我们通过一个具体的例题说明思想方法.12例2.1(1) 4213→(301)4后面比4小的数的个数a 3=3; 3后面比3小的数的个数a 2=0; 2后面比2小的数的个数a 1=1.(2) (301) →4213由a 3=3知1,2,3都在4的后面; 由a 2=0知1,2都在3前面; 由a 1=1知1在2后面.(3) (4213)↔(a 3a 2a 1)=(301).2. 字典序法对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。

排列组合公式/排列组合计算公式排列 P------和顺序有关组合 C -------不牵涉到顺序的问题排列分顺序,组合不分例如把5本不同的书分给3个人,有几种分法. "排列"把5本书分给3个人,有几种分法"组合" 1．排列及计算公式从n个不同元素中，任取m(m≤n)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 p(n,m)表示.p(n,m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)!(规定0!=1).2．组合及计算公式从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数.用符号c(n,m) 表示.c(n,m)=p(n,m)/m!=n!/((n-m)!*m!)；c(n,m)=c(n,n-m);3．其他排列与组合公式从n个元素中取出r个元素的循环排列数＝p(n,r)/r=n!/r(n-r)!.n个元素被分成k类，每类的个数分别是n1,n2,...nk这n个元素的全排列数为n!/(n1!*n2!*...*nk!).k类元素,每类的个数无限,从中取出m个元素的组合数为c(m+k-1,m).排列（Pnm(n为下标，m为上标)）Pnm=n×（n-1）....（n-m+1）；Pnm=n！/（n-m）！（注：！是阶乘符号）；Pnn（两个n分别为上标和下标） =n！；0！=1；Pn1（n为下标1为上标）=n组合（Cnm(n为下标，m为上标)）Cnm=Pnm/Pmm ；Cnm=n！/m！（n-m）！；Cnn（两个n分别为上标和下标） =1 ；Cn1（n为下标1为上标）=n；Cnm=Cnn-m2008-07-08 13:30公式P是指排列，从N个元素取R个进行排列。