排列组合的生成.ppt
《排列组合的生成.ppt》由会员分享,可在线阅读,更多相关《排列组合的生成.ppt(19页珍藏版)》请在三一文库上搜索。
1、1.2 排列组合生成算法,全排列的生成算法 组合的生成算法 一般排列的生成算法,1. 全排列的生成算法,全排列的生成算法就是对于给定的字符集,用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。,这里介绍4种全排列算法:,(A) 直接生成法 (B) 序数法 (C) 字典序法 (D) 换位法,递推算法: 假设已经生成n-1个数的所有(n-1)!个全排列, 将n插入到每一个排列的前面、第12之间、第23之间、。 最后,即得到n个数的所有n(n-1)!=n! 个全排列。,优点是生成简便,缺点是速度慢。,(A) 直接生成法,n的p进制表示:,(B) 序数法,n的十进制表示:,我们来看另一种表示,n!
2、=(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)!+22!+2!,不难证明,从0到n!-1的任何数m可唯一的表示为,其中,所以从0到n!-1的n!个整数与,(an-1,an-2,a2,a1),一一对应。,从m计算出an-1,an-2,a2,a1的算法如下:,.,反过来, 由(a3,a2,a1)= (301)也可以得到排列4213,,下面我们试图将n-1个元素的序列(an-1,a1)与n个元素的排列建立起一一对应关系。,例如:p=4213 (a3,a2,a1)= (
3、301),序列(an-1,a1)与某一排列p=p1p2pn之间的对应关系为: ai 表示排列p中的数i+1所在位置的右边比它小的数的个数。,_ _ _ _,4,3,2,1,而a2=0,说明3的右边没有比它更小的,故3放在最右端,,考虑a1=1,容易得出,2右边还有一个空格放1,于是得到了排列4213。,由a3=3, 知4放在空格的最左端,这个算法的优点是建立了自然序数和排列之间的一一对应关系(通过n-1个元素的序列(an-1,a1) )。 缺点是这种对应关系需要通过序列转换,即两层对应关系,多一层计算量。,一个全排列可看做一个字符串,字符串可有前缀、后缀。关键是如何生成给定全排列的下一个排列。
4、,(C) 字典序法,字典序:对于两个序列a1ak和b1bk ,若存在t,使得ai=bi, it,但atbt ,则称,例如对于字符集1,2,3,较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321,所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀,也即变化限制在尽可能短的后缀上。,839647521的下一个为839651247。,例如:839647521是1-9的一个排列,求出下一个。,(1-9的排列最前面的是123456789,最后面的是987654321,从右向左扫描若都是增的,就到了987654321,也就没
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 排列组合 生成
链接地址:https://www.31doc.com/p-2591484.html