组合数学之排列组合生成算法教学课件_第1页
组合数学之排列组合生成算法教学课件_第2页
组合数学之排列组合生成算法教学课件_第3页
组合数学之排列组合生成算法教学课件_第4页
组合数学之排列组合生成算法教学课件_第5页
已阅读5页，还剩53页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

(★)《组合数学》第二研民|糠列甑合生戚依第二讲:排列组合的生成箕法组合数学的主要问题:(1)存在:;满足一定条件配置的存在性(2)计数:计算出满足条件配置的数目(3)算法:构造所有配置的算法(4)优化:优化算法一.排列生成算法●排列生成有几种典型算法,这些算法都很有成效它们在实际中具有广泛应用价值.1.序数法2.字典序法3.邻位互换法(Johnson-Trotter4.轮转法1.序数法●序数法基于一一对应概念●先在排列和一种特殊的序列之间建立一种一一对应关系,然后再给出由序列产生排列的方法●因为序列的产生非常方便,这样我们就可以得到一种利用序列来生成排列的方法●如何建立这种一一对应?●思路类似数的10进制、2进制和p进制表示∑q,10,0≤a,≤9;k=0∑a2,0≤a≤1;k=0n-1n=∑akp",0≤ak≤Pk=0●这相当于自然数与某种序列之间建立了一一对应关系●可以利用置换来表示整数:n!=n(m-1)!=(n-1+1)(m-1)!=(n-1)(-1)!+(n-1)!(n-1)!=(n-2)(m-2)!+(n-2)n!=(-1)(-1)!+(n-2)(n-2)!+(-3)(n-3)!+…+202!+11!+1●n!-l=(n-1)(n-1)!+(n-2)(m-2)!+(-3)(-3)!+…+2·2!+11!●可以证明,从0到n!-1之间的任何整数m都可唯一地表示为:m=n1(-1)+an2(-2)+,,+a2°2!+a11!其中0<,=1,2,…,-1●m与序列(an14n2,…,.23a1)一对应●书中有确定这些系数的方法●例如:10=13:+22:+01●因为满足条件0≤a≤i,1sn-1(2.1)的序列共有n!个,这恰好与0到n!-1的m!个整数对应●需要建立满足条件(21)的m!个序列an-Isa2…,a2a1)和n元集合S的全部排列之间的一一对应关系.●还需要给出一种办法,由每个满足条件(21)的序列(aia2…,a2a)可生成唯的一个排列.●这样我们就可以产生出所有的排列●怎么样由一个满足条件(21)的序列产生一个n阶排列?如何把1,2的一个排列与一个满足条件(21)的序列建立起直接的关系?行列式定义中有逆序数的概念,就是个排列中违反自然顺序的数对:比如12354的逆序数为1,而43215的逆序数为6●设p2…Dn是任意一个n元排列,则+1后面比计1小的数字的个数a2总不超过;,

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论