组合数学之排列组合生成算法

组合数学之排列组合生成算法

《组合数学》 组合数学》第二讲

排列组合生成算法

组合数学之排列组合生成算法

第二讲: 第二讲: 排列组合的生成算法组合数学的主要问题: 组合数学的主要问题: (1) 存在: 满足一定条件配置的存在性. 存在: 满足一定条件配置的存在性. (2) 计数：计算出满足条件配置的数目. 计数：计算出满足条件配置的数目. (3) 算法：构造所有配置的算法. 算法：构造所有配置的算法. (4) 优化：优化算法. 优化：优化算法.2

组合数学之排列组合生成算法

一. 排列生成算法排列生成有几种典型算法, 排列生成有几种典型算法, 这些算法 都很有成效. 都很有成效. 它们在实际中具有广泛 应用价值. 应用价值. 序数法 字典序法 邻位互换法(Johnson邻位互换法(Johnson-Trotter) 轮转法3

1. 2. 3. 4.

组合数学之排列组合生成算法

1. 序数法序数法基于一一对应概念. 序数法基于一一对应概念. 先在排列 和一种特殊的序列 排列和一种特殊的 序列之间建立 先在 排列 和一种特殊的 序列 之间建立 一种一一对应关系, 一种一一对应关系 , 然后再给出由序列 产生排列的方法 因为序列的产生非常方便, 因为序列的产生非常方便 , 这样我们就 可以得到一种利用序列来生成排列的方 可以得到一种利用序列来生成排列的方 法. 如何建立这种一一对应? 如何建立这种一一对应?4

组合数学之排列组合生成算法

思路类似数的10进制、 进制和p 思路类似数的10进制、2进制和p进制 进制 表示. 表示.

n = ∑ak 10 , 0 ≤ak ≤ 9;k k =0

m 1

n = ∑ak 2 , 0 ≤ak ≤ 1;k k=0

m 1

n = ∑ak p , 0 ≤ak ≤ p 1.k k =05

m 1

组合数学之排列组合生成算法

这相当于自然数与某种序列之间建立 了一一对应关系. 了一一对应关系. 可以利用置换来表示整数: 可以利用置换来表示整数: n!=n(n- =(n-1+1)(nn!=n(n-1)! =(n-1+1)(n-1)! = (n-1) (n-1)!+(n-1)! (n- (n-1)!+(n(n-1)!= (n-2) (n-2)!+(n-2)! (n(n- (n-2)!+(nn!= (n-1) (n-1)!+ (n-2) (n-2)! (n- (n(n- (n+ (n-3) (n-3)!+ …+2 2!+1 1!+1 (n- (n 2!+16

组合数学之排列组合生成算法

n!-1=(n-1) (n-1)! +(n-2) (n-2)! n!- =(n- (n- +(n- (n+(n-3) (n-3)!+ …+2 2!+1 1! +(n- (n-3)!+ 2!+1 1! 可以证明, 之间的任何整数m 可以证明, 从0到n!-1之间的任何整数m 都可唯一地表示为: 都可唯一地表示为: m=an-1 (n-1)!+an-2 (n-2)!+…+a2 2!+a1 1! 1)!+ 2)!+ 2!+ 其中0 其中0≤ai≤i, i=1,2, …,n-1. m与序列(an-1,an-2 ,…a2,a1)一一对应 与序列( 书中有确定这些系数的方法. 书中有确定这些系数的方法. 例如：10= 例如：10=1 3! + 2 2! + 0 1!7

组合数学之排列组合生成算法

因为满足条件 0≤ai≤i, 1≤i≤n-1 1≤ 2.1) (2.1) 的序列 (an-1, an-2, …, a2, a1) 共有n 这恰好与0 共有n!个, 这恰好与0到n!-1的n!个整数一 一对应. 一对应. 需要建立满足条件(2.1)的 需要建立满足条件(2.1)的n!个序列 (an-1, an-2, …, a2, a1)和n元集合S的 元集合S 全部排列之间的一一对应关系. 全部排列之间的一一对应关系.8

组合数学之排列组合生成算法

还需

要给出一种办法, 还需要给出一种办法, 由每个满足条件 (2.1)的序列 (2.1)的序列(an-1,an-2, …,a2,a1)可生成唯 的序列( 一的一个排列. 一的一个排列. 这样我们就可以产生出所有的排列. 这样我们就可以产生出所有的排列. 怎么样由一个满足条件(2.1)的序列产 怎么样由一个满足条件(2.1)的序列产 生一个n阶排列? 生一个n阶排列? 如何把1,2,…,n 如何把1,2,…,n的一个排列与一个满足 条件(2.1)的序列建立起直接的关系 的序列建立起直接的关系? 条件(2.1)的序列建立起直接的关系?9

组合数学之排列组合生成算法

行列式定义中有逆序数的概念, 行列式定义中有逆序数的概念, 就是一 逆序数的概念 个排列中违反自然顺序的数对: 个排列中违反自然顺序的数对: 比如 12354的逆序数为 12354的逆序数为1, 而43215的逆序数 的逆序数为1 43215的逆序数 为6. 是任意一个n元排列, 设p1p2…pn是任意一个n元排列, 则i+1 后面比i+1小的数字的个数 总不超过i 小的数字的个数a 后面比i+1小的数字的个数ai总不超过i, =1,2,…,n 即ai≤i, i=1,2,…,n-1. 这样自然由一个排列得到一个序列 (an-1,an-2,…,a2,a1), 而且满足条件(2.1). 而且满足条件(2.1).10

组合数学之排列组合生成算法

我们可以如下建立序列与排列的对应: 我们可以如下建立序列与排列的对应: 满足条件( 设序列 (an-1,an-2, …,a2,a1)满足条件(2.1). 则它所对应的排列为(p)=p 则它所对应的排列为 (p)=p1p2…pn, 其 可以看作是排列(p) 中数 中数i 中 ai 可以看作是排列 (p)中数 i+1 所在位 置后面比i 小的数的个数. 置后面比i+1小的数的个数. 要说明这种对应的合理性, 必须清楚. 要说明这种对应的合理性 , 必须清楚 . 如何由序列产生出它所对应的排列. 如何由序列产生出它所对应的排列. 我们通过一个具体的例题说明思想方 法.11

组合数学之排列组合生成算法

例2.1 (1) 4213 →(301) 4后面比4小的数的个数a3=3; 3后面比3 后面比4小的数的个数a =3; 后面比3 小的数的个数a =0; 后面比2 小的数的个数a2=0; 2后面比2小的数的 个数a =1. 个数a1=1. (2) (301) → 4213 =3知1,2,3都在 的后面; 都在4 =0知 由a3=3知1,2,3都在4的后面; 由a2=0知 1,2都在 前面; 1,2都在3前面; 由a1=1知1在2后面. 都在3 …… 此处隐藏：1887字，全部文档内容请下载后查看。喜欢就下载吧 ……