排列组合与生成算法 .ppt

1.6全排列的生成算法 全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。 1.6全排列的生成算法 这里介绍3种全排列算法： 1.6.1序数法 n的十进制表示： 我们来看另一种表示 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! 不难证明，从0到n!-1的任何数m可唯一的表示为 m=an-1(n-1)!+ an-2(n-2)!+…+a11!, 其中0 ai i. 所以从0到n!-1的n!个整数与 (an-1,an-2,…a2,a1) 一一对应。另一方面，不难从m算出an-1,an-2,…a2,a1. 算法如下： m=m1, 0≤ m ≤n!-1 m1=2m2+k1, 0≤ k1 ≤1 m2=3m3+ k2, 0≤ k2 ≤2 ……………. mn-2=(n-1)mn-1+ kn-2, 0≤ kn-2 ≤n-2 mn-1= kn-1, 0≤ kn-1 ≤n-1 (kn-1 … k2k1) ←→ m 下面我们试图将n-1个元素的序列(an-1,…,a1)与n个元素的排列建立起一一对应关系 设序列(an-1,…,a1)对应某一排列p=p1p2…pn, 其中 ai：排列p中数i+1所在位置的右边比i+1小的数的个数,i=1,2,…,n-1 例 p=4213 --?(a3,a2,a1)= (301) 由a3=3, 4放在空格的最左端, _ _ _ _ 实际上，我们可以从1开始构造排列 1，写下 1 2，考虑a1 ,它只可取0或1，若取0，则2必在1的后边，否则，它在1的前边。 3，考虑a2, 它可取0,1,2.若取0，3必放在上一步得到的两个数的排列的后边， 若a2=1,则3必放在第二步得到的两数的排列的中间，若a2=2,则3必放在第二步得到的排列的两数的前边， … k+1，考虑ak,0 ≤ ak ≤ k, (1), ak=0, k+1必放在第k步得到的排列的这k个数的最后面； (2), ak=1, k+1必放在第k步得到的排列的这k个数的倒数两个数中间， …. (j), ak=j, k+1必放在第k步得到的排列的这k个数的倒数j, j+1这两个数之间；…. 1.6.2字典序法 对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。 1.6.2字典序法 [例]字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是: 123,132,213,231,312,321。 1.6.2字典序法 1）生成给定全排列的下一个排列 所谓一个的下一个就是这一个与 下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。 1.6.2字典序法 [例] 839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下 一个了。否则找出第一次出现下降的位置。 1.6.2字典序法 求839647521的下一个排列 1.6.2字典序法 一般而言，设P是[1,n]的一个全排列。 1.6.3换位法 思想 [n]的全排列可由[n-1]的全排列生成： 给定[n-1]的一个排列п,将n 由最右端依次插入排列п ，即得到n个[n]的排列： (1) 1 1 1 1 2 3 1 2 3 1 2 3 1 2 3 1 3 2 1 3 2 1 3 2 1 3 2 3 1 2 3 1 2 3 1 2 3