第　5　章组合数学基础组合数学是现代数学的一个重要分支,研究的主要内容是有限、可数或离散对象。计算机科学的一个重要方向就是通过算法对离散数学问题进行加工和处理。随着计算机科学的发展,组合数学在计算机科学中的作用也日益凸显。排列和组合是组合数学中最基本的概念,本章主要介绍排列和组合生成的基础算法。 5.1　排列生成算法将n 个元素(或符号)按照确定的顺序进行重排,重排后的所有顺序称为全排列。图5-1 给出了集合为{1,2,3,4}时的全排列示意图。图5-1 集合为{1,2,3,4}时的全排列示意图全排列生成都遵循着原排列→映射规则→新排列的基本过程。全排列生成过程中, 映射规则最为关键,不同映射规则决定了生成全排列的不同算法。常用的全排列生成算法包括序数生成法、字典序生成法、邻位互换法和轮转生成法等算法,本节只介绍序数生成法和字典序生成法两类。 5.1 序数生成法 1. 基于序数的全排列生成算法,其核心思想是建立集合 S 的全排列与某一规则 R 所生成序列间的一一映射关系。建立映射时通常采用类似进制转换的方法,详细推导过程读者可参考组合数学相关书籍,本节只给出概要描述。 s1,sn 设p1p2…pn 为包含 n 个元素的集合S={s2,…,}的一个排列,规则 R 定义如下。 ①对p1p2…pn 按值降序排列生成新的序列p'''。 1p2…pn ②规则 R 的生成序列为a与p2…p'的映射关系为 n-1an-2…a1, 1p'(') n 2,…,其中a为p在排列p1p2…pn 的逆序数。 an-'a2.pa1.pn-n-' 1.p1,n-''1, ii 逆序数是指排列中在值 k 右侧却比 k 小的元素的个数,如4213 中4的逆序数为3,2 的逆序数为1。p'值最小,没有逆序数,因而 R 的生成序列an-n-2…a1 中没有关于p'n 的 n 1a 映射。序数生成法生成全排列有以下两个关键点。 (1)以阶乘为基的整数表示方法。 n 个数的全排列共有n!个,用0~n!-1表示。设 m 为0~n!-1中的任意值,则 m 可表示为1!,2!,…,(n-1)! 的线性组合,即 m =an-1(n-1)!+an-2(n-2)!+…+ a11!, 其中0≤ai≤i。 m 与唯一序列(一一对应。 (2)逆序和排列一一对应。 an-1an-2…ai…a1) 因为排列的逆序和排列一一对应,所以排列的逆序就可以通过序列an-1an-2…ai … a1 唯一表示。例如,当排列p1p2p3p4=4213 时,p'1p'2p'3=432,此时a3.p'1=4,逆序数有2,1和 a2.p2=a1.p3= 3,所以a3=3;'3没有逆序数,所以a3=0;'2,逆序数为1,所以有a1= 1。因此,排列p1p2p3p4=4213 对应的逆序序列为排列a3a2a1=301 。再例如,已知S={1,2,3,4}, 逆序序列为a3a2a1=301,求对应的排列p1p2p3p4。由S={1,2,4}可知, ' 4。因为a3=3,可以确定在4右侧且小于4的元素有3 3,a3.p1= a2.p2= 个,所以4在排列的第1位; ' 3且a2=0,可以确定在3右侧且小于3的元素有0 个,所以3在排列的第4位;3=2且a1=可以确定在2右侧且小于2的元素有1 a1.p' 1, 个,所以2在排列的第2位;最后一位1排在第3位。表5-1给出了有4个元素的集合 S={1,2,3,4}的全排列的映射。 91 92 表5-1 集合S={1,2,3,4}的全排列的映射序号a3a2a1 p1p2p3p4 序号a3a2a1 p1p2p3p4 序号a3a2a1 p1p2p3p4 0 000 1234 8 110 1342 16 220 3412 1 001 2134 9 111 2341 17 221 3421 2 010 1324 10 120 3142 18 300 4123 3 011 2314 11 121 3241 19 301 4213 4 020 3124 12 200 1423 20 310 4132 5 021 3214 13 201 2413 21 311 4231 6 100 1243 14 210 1432 22 320 4312 7 101 2143 15 211 2431 23 321 4321 序数法生成排列算法代码中GenReverse()函数的功能是由整数生成以阶乘为基的逆序序列,整数与逆序序列的对应关系如表5-1所示。逆序序列递增a1a2…an-1的实际生成顺序与算法描述相反,输出时逆序即可。GenReverse()函数有3个参数,reverses[] 是结果数组,下标从1开始,实际长度为n;N 为待处理整数;len为结果数组的长度。 GenPermutation()函数的功能是由逆序序列生成排列,生成方法可参考文献[7]对应章节的内容。GenReverse()函数有3个参数,permutation[]数组保存待生成的排列,下标从1开始,长度为n+1;reverses[]保存已经生成的逆序数组,下标从1开始,实际长度为n;len为结果数组的长度。实现代码如下。 #include #include using namespace std; void GenReverse(int reverses[], int N, int len) { int i; for (i = 1; N > 0; i++) { reverses[i] = N % (i + 1); N = N / (i + 1); } while (i <= len - 1) { reverses[i++] = 0; } }v oid GenPermutation(int permutation[], int reverses[], int len) { int i, j; for (i = 0; i <= len; i++) //将排列数组重置为0 93 permutation[i] = 0; for (i = len - 1; i >= 1; i--) { //下标j:从p 的右(下标最大)侧向左(下标小)第1 个未被占用的元素开始数,数a[i]个数位 j = len; while (true) { if (permutation[j] == 0) { reverses[i]--; if (reverses[i] < 0) break; } j--; } permutation[j] = i + 1; //将该数位的值置为i+1 } for (i = 1; i <= len; i++) //最后一个元素位置填上1 { if (permutation[i] == 0) permutation[i] = 1; } }v oid DisplayResults(const char s[], int list[], int len, bool reverse) { int i; cout << s << endl; if (!reverse) { for (i = 1; i < len; i++) cout << " " << list[i]; } else { //逆序数组实际是按R1R2...Rn-1 方式存放,需逆序输出 for (i = len - 1; i >= 1; i--) cout << " " << list[i]; } cout << endl; }i nt main() { const int MAX_RECORDS = 10; //最多10 个元素 //下标从1 开始:逆序数组有9 个元素,排列数组有10 个元素 94 int rev[MAX_RECORDS], perm[MAX_RECORDS + 1]; int i, n, fact; cout << "请输入排列的位数值:"; cin >> n; fact = 1; for (i = 1; i <= n; i++) //求n 的阶乘 fact *= i; for (i = 0; i < fact; i++) //循环求出p 数组 { GenReverse(rev, i, n); //由整数生成以阶乘为基的表示结果 DisplayResults("逆序", rev, n, 1); //显示生成的逆序结果 GenPermutation(perm, rev, n); //根据逆序序列生成排列 DisplayResults("排列", perm, n + 1, 0); cout << endl; } return 0; } 5.1.2 字典序生成法字典序生成法就是按照字典顺序规定了字符集中字符的先后关系,并以此为基础规定两个全排列的先后顺序是从左至右逐个比较相应的字符来确定。设n 个元素的集合S={s1,s2,…,sn },其字典序的初始排列方案为P =p1p2…pn , 按照字典顺序得到P 的下一个排列方案Pnext,称为P 的一个置换。按照相同的转换方法重复n!-1次就可以获得n 个元素的全排列。从当前排列方案按照字典序获得下一字典序排列的置换方案表述如下。 (1)找到最后一个正序。找到最后一个正序末位可以表示为i=max{j|pjpj+2>…>pn 。 (2)在递减区寻找大于pi 的最小元素pk 。在递减区间pi+1pi+2…pn 中从右至左寻找大于pi 的最小元素pk ,即k=max{j|pj >pi}。对pi 右侧的递减序列而言,从右至左为递增,因此k 是所有大于pi 的数字中序号最大者。 (3)交换pi 与pk 。 (4)将原递减区升序排列。例如,令S={1,2,3,4},其某个字典序排列为P =3421,寻找下一个置换方案的过程如下。 (1)最末正序为i=max{j|pjpi}=2,p2=4; (3)交换p1 和p2,交换后序列为4321; 95 (4)升序排列原递减区间4321.4123。再例如,集合S={1,2,3,4,5,6,7,8,9}的某个字典序列p=146295873,下一个字典序的置换过程为146295873.146297853.146297358。 5.1.3 “火星人”问题人类终于登上了火星,并且见到了神秘的火星人。人类和火星人都无法理解对方的语言,科学家发明了一种用数字交流的方法。首先,火星人把一个非常大的数字告诉人类科学家,科学家破解这个数字的含义后,再把一个很小的数字加到这个大数上面,把结果告诉火星人,作为人类的回答。火星人用一种非常简单的方式来表示数字———掰手指。火星人只有一只手,但这只手上有成千上万的手指,这些手指排成一列,分别编号为1,2,…。火星人的任意两根手指都能随意交换位置,他们就是通过这种方法计数的。一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指———拇指、食指、中指、无名指和小指分别编号为1,2,3,4和5,当它们按正常顺序排列时,形成了5位数12345,当你交换无名指和小指的位置时,会形成5位数12354,当你把五个手指的顺序完全颠倒时,会形成54321,在所有能够形成的120个5位数中,12345最小,它表示1; 12354第二小,它表示2;54321最大,它表示120。表5-2展示了只有3根手指时能够形成的6个3位数和它们代表的数字。表5-2 手指数字与十进制数对应表三进制数123 132 213 231 312 321 数字 1 2 3 4 5 6 假如你有幸成为第一个和火星人交流的地球人。一个火星人会让你看他的手指,科学家会告诉你要加上去的很小的数。你的任务是把火星人用手指表示的数与科学家告诉你的数相加,并根据相加的结果改变火星人手指的排列顺序。这是一道典型的字典序生成全排列问题。为此,添加了SwapArrayElements()函数和SelectionSort()函数作为辅助函数。SwapArrayElements()函数用于交换数组内两下标所对应的元素,SelectionSort()函数用于实现对给定区间进行选择排序。 SwapArrayElements()函数有3个参数,data[]为保存生成序列的数组,idx和idy为待交换的两元素对应的下标,就是pi 和pk 对应的下标。SelectionSort()函数有3个参数,data[]为待排序数组,start为排序的起始下标,len为待排序长度。按照字典序生成全排列的关键函数为GetNextPermutation()。GetNextPermutation() 在当前排列的基础上生成下一个置换,生成方法如前所述。GetNextPermutation()函数有两个参数,data[]为当前排列,count为排列中元素的总数。实现代码如下。 #include #include using namespace std; //交换数组中下标为idx 和idy 的两个元素 96 void SwapArrayElements(int data[], int idx, int idy) { int t = data[idx]; data[idx] = data[idy]; data[idy] = t; } //data[]为待排序数组,start 为排序的起始下标,len 为待排序长度 void SelectionSort(int data[], int start, int len) { int i, j, temp; for (i = start; i < start + len; i++) { int min = i; for (j = i + 1; j < start + len; j++) //遍历未排序的元素 if (data[j] < data[min]) //保存目前最小值下标 min = j; if (min != i) //若最小值不是当前位置则交换 { temp = data[min]; data[min] = data[i]; data[i] = temp; } } }b ool GetNextPermutation(int data[], int count) //下标从1 开始 { int i = count; //查找递减区间起始位置 while (data[i] < data[i - 1]) i--; i--; //在递减区间内找到与data[i]最接近值的下标position int min = INT_MAX, position = 0; for (int k = i + 1; k <= count; k++) { if (min > data[k] - data[i] && data[k] > data[i]) { position = k; min = data[k] - data[i]; } if (position == 0) return false; } //置换 97 SwapArrayElements(data, i, position); //对原递减区域按升序排序 int start = i + 1; SelectionSort(data ,start, count - start + 1 ); return true; }i nt main() { const int MAX_ELEMENTS = 40000; int elements[MAX_ELEMENTS]; int count, perms; cin >> count; cin >> perms; for (int i = 1; i <= count; i++) cin >> elements[i]; for (int i = 1; i <= perms; i++) if (!GetNextPermutation(elements, count)) break; for (int i = 1; i <= count; i++) cout << elements[i] << " "; return 0; } 运行结果如下。 5.2　组合生成算法组合是组合数学中最基本的概念之一。从含有n 个元素的集合S={s1,s2,…,sn }中任取m 个作为一组(不考虑组内元素间的排列顺序),称为S 的一个m 组合,记作Cm n (也有n 和m 位置调换的表示方法)。从n 个元素取出m 个所构成的组合数量用式(5.1) 表示。 Cm n =n(n -1)(n -2)…(n -m +1) m (m -1)(m -2)…1 = n! m ! (n -m )! (5.1) 因为组合中不考虑元素间的排列次序,m 个元素的排列数为m !,所以分母为m !。组合具有以下两条性质: (1)Cm n =Cn-m n ; (2)Cm n =Cm n-1+Cnm--11。性质(1)可以自己推导得出。性质(2)也可以理解为从n 个元素取出m 个,有如下两种情况:①不考虑第n 个元素,只从前n-1个元素中取m 个;②选择第n 个元素,再从前n-1个元素中取m-1个。 5.1 基于字典序的组合生成算法 2. 与排列相比,组合的生成要容易得多。表5-3给出从S={1,2,3,4,5,6}中任取3个元素的组合结果。表5- 3 从 S 中任取3个元素的组合序号c1c2c3 序号c1c2c3 序号c1c2c3 1 123 8 145 15 246 2 124 9 146 16 256 3 125 10 156 17 345 4 126 11 234 18 346 5 134 12 235 19 356 6 135 13 236 20 456 7 136 14 245 观察表5-3中的每个组合c1c2c3,可以发现c1c2c3 满足条件1≤c1 ubound)分支结构的作用是判定整个组合生成过程是否结束。while 循环用来处理组合后面数位上的值超出上限的情况。实现代码如下。 #include using namespace std; bool NextCombination(int comb[], const int n, const int m) { //所有元素值比实际输出值小1,输出时调整 int i = m - 1; //组合最后一个元素的下标 //组合第1 元素的上限 const int ubound = n - m; //比实际输出值小1,输出时补偿1 do { comb[i]++; } while (comb[i] > ubound + i && i--); //若第1 位也已经到达上界,则组合生成完毕 if (comb[0] > ubound) return false; //调整i 位之后其余位:aj<-aj-1+1, while (++i < m) comb[i] = comb[i - 1] + 1; return true; }