第6章-组合数学中的程序设计.ppt

第六章 组合数学中的程序设计 沈云付 yfshen@staff.shu.edu.cn 本章主要内容 6.1 组合数学中有关概念与公式 6.1.1 排列与组合及有关的生成算法 6.1.2 母函数 6.1.3 容斥原理与错排 6.1.4 Polya定理 6.2 实例研究 6.1 组合数学中有关概念与公式 6.1.1 排列与组合及有关的生成算法 1．排列与组合的基本概念和公式 排列、相异元素可重复的排列 组合、相异元素可重复的组合 6.1.1 排列与组合及有关的生成算法 在多项式 的展开式中的项 的系数 不定方程 的有非负整数解的个数为 设n是一个正整数，令Qn表示在{1，2，…，n}中不允许出现两个连续数字的排列方法数，则有Qn = 6.1.1 排列与组合及有关的生成算法 2．全排列的生成算法 全排列的生成算法有：字典序法、递增进位制数法、递减进位制数法和邻位对换法等 全排列的字典序算法 问题：对于给定的一个全排列P，要生成P的下一个排列Q 6.1.1 排列与组合及有关的生成算法 字典序全排列： 给定n个元素的集合{x1，x2，x3，…，xn}，对X中的元素规定了一个先后关系。在两个排列中，按字典序方式对它们的位从左到右每位比较，较小的字符对应的排列较先，按这样的序生成的全排列称为字典序全排列。 给定排列P，求下一个排列Q 例：求X={1，2，3，4，5，6，7}上排列P= 2637541的下一个排列Q 从右到左找出比右边数字小的第一个数，即3。 再从右到左考察比3大的第一个数，是4 将3与4对换位置，得2647531 将得到的排列2647531从4后面的7531翻转得1357 把前缀264接在1357的前面得2641357，它就是所求的排列2647531的下一个排列。 给定排列P，求下一个排列Q算法 设X={1，2，…，n}，求P=a1a2…an的下一个排列：： 在P中从右到左寻找右边比左边大的数的第一个位置j，即j=max{i|aiai+1} 在P中从右到左寻找比aj大的数的第一个位置k，即k=max{i|aiaj}。此时排列P形如a1a2…aj-1aj aj+1…ak-1 akak+1…an。 对换aj，ak，并将aj+1…ak-1ajak+1…an翻转，得Q= a1a2…aj-1akan…ak-1ajak+1…an即为P的下一个排列。 6.1.1 排列与组合及有关的生成算法 3.组合的生成算法 令j= max{i| ai＜n-m+i+1}。那么a1a2…am的下一个组合为a1a2…aj-1(aj+1)(aj+2)…(aj+m-j)。 例如，给定n=13，m= 6，组合4 5 7 8 12 13，于是可见j=3。将8 12 13依次修改为9 10 11。那么组合4 5 7 8 12 13的下一个组合为4 5 7 9 10 11。 6.1.1 排列与组合及有关的生成算法 4.字典序全排列与序号的转换 字典序全排列的序号 记P=a1a2…an。记ki为元素ai的逆序数，则排列P的序号为 给定排列的序号 //给定元素个数n，及全排列p //返回字典序全排列下排列序号num int perm2num(int n, int *p){ int i, j, num=0,k=1; for (i=n-2;i=0;k*=n-(i--))//因子为(n-i-1)!，注意下标从0开始 for (j=i+1;jn;j++) if (p[j]p[i]) num+=k;//是否有逆序，如有，统计 return num; } 给定排列的序号求排列 //给定元素个数n，排列序号num //返回对应的排列p void num2perm(int n, int *p,int num){ int i,j; //求逆序数数组 for(i=n-1;i=0;i--)p[i]=num%(n-i),num/=n-i; for (i=n-1;i;i--) for (j=i-1;j=0;j--) if (p[j]=p[i]) p[i]++; //根据逆序数数组进行调整 } 6.1.1 排列与组合及有关的生成算法 5．字典序组合与序号的转换 实例：设n=9，m=4。将从n个元素取m个的所有组合从1开始从小到大编序，组合3 5 7 9的序号是多少？ 一种计算方法：首位小于3的组合的个数为91；首位是3，第2位小于5的组合的个数为10；前2位是3 5，第3位小于7的组合的个数为3；前3位是3 5 7，第4位小于9的组合的个数为1。所有这些数之和105，加上它本身的1个号，得组