组合数学：1-2 排列组合的生成

时间：2025-05-07

北京邮电大学组合数学课件

1.2 排列组合生成算法1. 全排列的生成算法 2. 组合的生成算法

3. 一般排列的生成算法

北京邮电大学组合数学课件

1. 全排列的生成算法全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。这里介绍4种全排列算法： (A) 直接生成法 (B) 序数法 (C) 字典序法 (D) 换位法

北京邮电大学组合数学课件

(A) 直接生成法递推算法：假设已经生成n-1个数的所有(n-1)!个全排列，将n插入到每一个排列的前面、第12之间、第23 之间、。。。最后，即得到n个数的所有n(n-1)!=n! 个全排列。优点是生成简便，缺点是速度慢。

北京邮电大学组合数学课件

(B) 序数法i n的十进制表示： n a i 10 , 0 a i 10 k

n的p进制表示： n a i p i , 0 a i pi 1

i 1 k

我们来看另一种表示n!=((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)!+…+2×2!+2!即 n ! 1

k k!k 1

n 1

北京邮电大学组合数学课件

不难证明，从0到n!-1的任何数m可唯一的表示为m a n 1 ( n 1)! a n 2 ( n 2)! ... a1 1!

其中0 a i i , i 1,..., n 1.

所以从0到n!-1的n!个整数与

(an-1,an-2,…a2,a1)一一对应。

北京邮电大学组合数学课件

从m计算出an-1,an-2,…a2,a1的算法如下：m m1 , 0 m n ! 1 0 a1 1 0 a2 2 0 a n 2 n 2 m 1 2 m 2 a1 , m 2 3 m3 a2 ,

…………….m n 2 ( n 1) m n 1 a n 2 , m n 1 a n 1 , 0 a n 1 n 1

( a n 1 , a n 2 ,..., a 2 , a1 ) m

北京邮电大学组合数学课件

下面我们试图将n-1个元素的序列(an-1,…,a1)与n个元素的排列建立起一一对应关系。序列(an-1,…,a1)与某一排列p=p1p2…pn之间的对应关系为： ai 表示排列p中的数i+1所在位置的右边比它小的数的个数。

例如：p=4213 (a3,a2,a1)= (301)反过来, 由(a3,a2,a1)= (301)也可以得到排列4213,

北京邮电大学组合数学课件

由a3=3, 知4放在空格的最左端,

4 2 1 3 _ _ _ _而a2=0,说明3的右边没有比它更小的，故3放在最右端，考虑a1=1,容易得出，2右边还有一个空格放1,于是得到了排列4213。这个算法的优点是建立了自然序数和排列之间的一一对应关系(通过n-1个元素的序列(an-1,…,a1) )。缺点是这种对应关系需要通过序列转换，即两层对应关系，多一层计算量。

北京邮电大学组合数学课件

例如对于字符集{1,2,3},较小的数字较先，这样按字典序生成的全排列是：123,132,213,231,312,321一个全排列可看做一个字符串，字符串可有前缀、后缀。关键是如何生成给定全排列的下一个排列。所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，

也即变化限制在尽可能短的后缀上。

北京邮电大学组合数学课件

例如：839647521是1-9的一个排列，求出下一个。 (1-9的排列最前面的是123456789,最后面的是 987654321,从右向左扫描若都是增的，就到了 987654321,也就没有下一个了。) (1) 从右向左扫描找出第一次出现下降的位置。(4) (2) 在4的右边按从左往右的顺序找出最后一个比4 大的数字(5),交换这两个数字，得到839657421。 (3) 把5后面的数字顺序完全颠倒过来即得到：

839647521的下一个为839651247。

北京邮电大学组合数学课件

一般而言，设P是[1,n]的一个全排列。

P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pn(1) 找出 j=max{ i |Pi<Pi+1},k=max{ i |Pi>Pj}; (2) 对换 Pj,Pk; (3) 将 Pj+1…Pk-1PjPk+1…Pn翻转， P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即是P的下一个。该算法的优点是排列清晰，而且保持着字典序。缺点是算法较繁琐。

北京邮电大学组合数学课件

(D) 换位法基于直接生成法，[n]的全排列可由[n-1]的全排列生成：给定[n-1]的一个排列 ,将n 由最右端依次插入排列п,即得到n个[n]的排列： p1 p2…pn-1n p1 p2…npn-1

…np1 p2…pn-1

北京邮电大学组合数学课件

例如对于 n=4 第一步：第二步：第三步： 1 1 2 2 1

1 2 3 13 2 31 2 32 1 2 31 2 1 3

北京邮电大学组合数学课件

第四步： 1 2 3 4 1 2 4 3 1 4 2 3 41 2 3 3 2 41 1 4 3 2 1 34 2 1 3 2 4 3 1 2 4 3 1 4 2 3 4 1 2 43 1 2

43 2 1 3 42 1 3 24 1 3 2 14 2 3 14 2 34 1 243 1 42 3 1 42 1 3 241 3 2 143 2 1 34

北京邮电大学组合数学课件

对上述过程，一般地，对于i,将前一步所得的每一排列重复 i 次，然后将 i 由第一排的最后往前移，至最前列，正好走了 i 次,下一个接着将 i 放在下一排列的最前面，然后依次往后移，一直下去即得 i 元排列。下面我们用较正式的语言来说这件事。

对给定的一个整数k,我们赋其一个方向，即在其上写一个箭头(指向左侧或右侧)