现代工程数学第4章.ppt

第 4 章 生成排列和组合 4.1 生成排列 4.2 排列中的逆序 4.3 生成组合 4.4 生成 r-组合 4.5 偏序和等价关系 作业 4.1 生成排列 集合 {1, 2, …, n} 的排列有 n! 个，当 n 增大时，n! 的值增加得很快。根据 Stirling 公式， n! ~ 本节讨论枚举{1, 2, …, n} 的所有排列的算法。该算法基于以下事实： 若将 n 从{1, 2, …, n} 的一个排列中删除，则得到 {1, 2, …, n ? 1} 的一个排列。 {1} 的排列 1 {1, 2} 的排列 1 2 2 1 {1, 2, 3} 的排列 1 2 3 ? 1 3 2 ? 3 1 2 2 1 3 ? 2 3 1 ? 3 2 1 {1, 2, 3, 4} 的排列 1 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 3 1 2 4 ? 3 1 4 2 ? 3 4 1 2 ? 4 3 1 2 3 2 1 4 ? 3 2 4 1 ? 3 4 2 1 ? 4 3 2 1 2 3 1 4 ? 2 3 4 1 ? 2 4 3 1 ? 4 2 3 1 2 1 3 4 ? 2 1 4 3 ? 2 4 1 3 ? 4 2 1 3 在集合 {1, 2, 3} 的一个排列中插入 4，可以生成集合{1, 2, 3, 4} 的 4 个排列，如由 1 2 3 可生成 1 2 3 4 1 2 4 3 1 4 2 3 4 1 2 3 一般说来，在集合 {1, 2, …, n ? 1} 的一个排列中插入 n ，可以生成集合 {1, 2, …, n} 的 n 个排列。 在前面生成集合 {1, 2, 3, 4} 的排列的过程中，从1 2 3 4 出发，每一步交换一对相邻整数，最后得出 2 1 3 4。 下面给出描述以上计算过程的算法。 给定一个整数 k，在它上面画一个向左或向右的箭头表示方向，如 或 。 考虑 {1, 2, …, n} 的排列，其中的每个整数都给定一个方向。若整数 k 的箭头所指的相邻数比它小，则称 k 为活动的。例如， 中只有 3, 5, 6 是活动的。显然，1 总是不活动的。只要存在所指的相邻数， n 总是活动的。 生成 {1, 2, …, n} 的排列的算法 从 开始。 当存在活动整数时，做 求出最大活动整数 m。 交换 m 与其所指向的相邻数。 改变所有大于 m 的整数的方向。 下面以 n = 4 为例执行该算法。 4.2 排列中的逆序 设 i1i2…in 是集合 {1, 2, …, n} 的排列。 若 k l 且 ik il，则称数对 (ik , il) 为一个逆序。 唯一没有逆序的排列是12…n 。 排列 31524 有 4 个逆序：(3, 1), (3, 2), (5, 2), (5, 4) 用 aj 表示排列在数 j 之前且比 j 大的数的个数，并称 a1, a2,…, an 为该排列的逆序列。 逆序数 a1 + a2 + … + an 量度该序列的无序程度。 排列 31524 的逆序列是 1, 2, 0, 1, 0。 集合 {1, 2, …, n} 的排列的逆序列 a1, a2,…, an 满足条件 0 ? a1 ? n ? 1, 0 ? a2 ? n ? 2, …, 0 ? an?1 ? 1, an = 0 满足这些条件的序列恰好有 n! 个，因为 a1有 n 种选择，a2 有 n ? 1 种选择, …, an 有 1 种选择。 我们让 {1, 2, …, n} 的每个排列映射到它的逆序列。如果能够证明每个满足这些条件的序列都是{1, 2, …, n} 的某个排列的逆序列，就说明所定义的映射是满射，这个满射一定是单射，所以是双射，即一一对应。 定理4.2.1 若 0 ? b1 ? n ? 1, 0 ? b2 ? n ? 2, …, 0 ? bn?1 ? 1, bn = 0 则存在唯一的 {1, 2, …, n} 的排列使得其逆序列是 b1 , b2 ,…, bn 。 证明 我们描述两个构造这样的排列的算法。 算法Ⅰ的缺点是，每个数在排列中的位置到最后才知道。 算法Ⅱ直接确定每个数在排列中的位置。 算法Ⅰ 从逆序列构造排列 n ：写出 n 。 n ? 1：若 bn ? 1 = 0，则将 n ? 1 放在 n 的前面； 若 bn ? 1 = 1，则将 n ? 1 放在 n 的后面。 …… n ? k：将 n ? k 放在第 bn ? k 个数的后面，这里第 0 个数的后面是指第 1 个数的前面。