组合数学第二讲

1、组合数学第二讲组合数学组合数学 第二讲第二讲排列算法和组合意义排列算法和组合意义排列的生成算法排列的生成算法 在实际工作中，需要将所有可能的排列一一罗列出在实际工作中，需要将所有可能的排列一一罗列出来加以分析，如何排列出来，需要有排列的生成算法。来加以分析，如何排列出来，需要有排列的生成算法。下面介绍几种排列的生成算法下面介绍几种排列的生成算法：1. 序数法序数法 2. 字典序法字典序法 3. 换位法换位法 1.序数法序数法 例例 1.11 以四个元素以四个元素1，2，3，4的排列为例，求其第的排列为例，求其第17个和第个和第 21个排列。个排列。解：四个元素解：四个元素 1，2，3，4 的第

2、一个排列为的第一个排列为 1 2 3 4，对应序列（，对应序列（0，0，0，0） 。） 。 和和17 116m 对应的序列为对应的序列为321(,)a a a，10a ，22a ，32a 。 因此，四个元素因此，四个元素 1，2，3，4 的第的第 17 个排列为个排列为 3 4 1 2。 和和21 120m 对应的对应的序列为序列为321(,)(3,1,0)a a a，10a ，21a ，33a 。因此，四个。因此，四个元素元素 1，2，3，4 的第的第 21 个排列为个排列为 4 1 3 2。 4 3 2 2. 字典序法字典序法 解：S1. 1max |2jjij pp S2. 1max |

3、2ikhk pp S3. 1p和2p互换得 4321 S4. 将 4321 中的 321 逆转得 4123 就是所求。 以1, 2, n的排序利用字典排序生成法，可从1, 2, n开始， 直到12 1n n 结束，即直到不存在1jjpp为止。 3. 换位法换位法 换位法看起来很直观，但比较繁琐。下面给出一个改进的算法换位法看起来很直观，但比较繁琐。下面给出一个改进的算法共参考使用：共参考使用： 对于对于1234的全排列，从的全排列，从1 2 和和2 1 开始先将开始先将3插入插入得得1 2 3 ，1 3 2，3 1 2和和2 1 3， 2 3 1，3 2 1，然后，然后将将4插入得：插入得：1

4、 2 3 4，1 2 4 3，1 4 2 3，4 1 2 3，1 3 2 4，1 3 4 2，1 4 3 2 ，4 1 3 2，。，。此法推及一般，也可算是生成排列算法的一种。此法推及一般，也可算是生成排列算法的一种。允许重复的组合允许重复的组合 不相邻的组合不相邻的组合 组合的生成组合的生成 组合的生成比排列要简单些。 已知12,rccc为一组不允许重复的组合，不妨假定 12rcccn，11rcn，22rcn，1,1cnr 或icnri ，1, 2,ir。而且存在12rccc，使 jcnrj ，rj 1.否则12,rccc已到最后一组，不存在后续的 组合。 组合意义的解释组合意义的解释 许多排列组合的公式很有实际意义，而且直观、富许多排列组合的公式很有实际意义，而且直观、富有启发。后面的讨论一般都指的是不允许重复的组合。有启发。后面的讨论一般都指的是不允许重复的组合。分析： （1）先从组合意义看这个公式 nr 看作是从(0, 0)点到(,)nr r点走的最短路径数， 1nr看作是从(0, 0)点到(1,)nrr 点走的最短路径数， 11nr看作是从(0, 0)点到(,1)nr r点走的最短路径数。 即从(0, 0)点到(,)nr r点走的最短路径由两部分路径组成，一部分是从(0, 0)点到(,1)nr r点走的最