计数原 4、计数原理 Counting 45排列与组合的生成 Generating Permutations and combinations 2/24/202111:38PM Deren Chen, Zhejiang UniV
计数原理 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 1 4、计数原理/Counting 4.5 排列与组合的生成 Generating Permutations and Combinations
计数 在实际应用中,往往不仅需要计数,而且要 把各种情况都枚举出来。 字典序排列/ lexicographic ordering for permutation 定义 顺序:排列a1,a2,…,an中相邻两数 a;<ai,称为一个顺序 逆序:排列a1,a2,,an中相邻两数 a;>a1,称为一个逆序。 2/24/202111:38PM Deren Chen, Zhejiang Univ 2
计数原理 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 2 在实际应用中，往往不仅需要计数，而且要 把各种情况都枚举出来。 一、 字 典序排 列/lexicographic ordering for permutation 定义: 顺序：排列ａ1，ａ2，…，ａn中相邻两数 ａi＜ａi+1，称为一个顺序。 逆序：排列ａ1，ａ2，…，ａn中相邻两数 ａi＞ａi+1，称为一个逆序
计数原 例: 排列132654 顺序:13,26,逆序:32,65,54 对n个对象进行全排列,有n!个排列,可 以对n个对象加上标记。 不失一般性,我们只需对n个自然数{1, 2,,n}进行全排列,枚举出所有的情况。 字典序排列算法 1.给出初始排列:p1=1,2,3,4,…,n 2.若pk已定义(1≤k≤n!-1) pk=al 2 a a 2/24/202111:38PM Deren Chen, Zhejiang Univ 3
计数原理 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 3 例： 排列１ ３ ２ ６ ５ ４ 顺序：１３，２６，逆序：３２，６５，５４。 对ｎ个对象进行全排列，有ｎ！个排列，可 以对ｎ个对象加上标记。 不失一般性，我们只需对ｎ个自然数｛１， ２，…，ｎ｝进行全排列，枚举出所有的情况。 １．给出初始排列：ｐ1＝１，２，３，４，…，ｎ ２．若ｐk已定义 (１≤ｋ≤ｎ！－１） ｐk＝ａ1，ａ2，…，ａm，…，ａn
计数 则按下列规定,定义p的下一个排列 p bi,b b n (1)寻找am:m=max{j|a<ait 即am,am1是最右面的顺序,自am1开始均为 逆序 (2)给出b;(i=1 a)第m项之前的项不变: b=a, b a。 b a bm=mi nala>am, p>m) 即在a右面大于an的项中选取最小的项作为bm 小到大排列,送入bbmm/d,…,an从 c)把am m+1 a p 2/24/202111:38PM Deren Chen, Zhejiang Univ 4
计数原理 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 4 则按下列规定，定义ｐk ｐk+1＝ｂ1，ｂ2，…，ｂm，…，ｂn (1)寻找ａm：ｍ＝ｍａｘ{ｊ|ａj＜ａj+1} 即ａm，ａm+1是最右面的顺序，自ａm+1开始均为 逆序。 (2)给出ｂi（ｉ＝１，２，…，ｎ） ａ） ｂ1＝ａ1，ｂ2＝ａ2，…，ｂm-1＝ａm-1 ｂ）ｂm＝ｍｉｎ{ａp|ａp＞ａm，ｐ＞ｍ） 即在ａm右面大于ａm的项中选取最小的项作为ｂm。 ｃ）把ａm，ａm+1，…，ａp-1，ａp+1，…，ａn从 小到大排列，送入ｂm+1，ｂm+2，…，ｂn
计数原 例1:设有n=6个数字的排列a1,a2, a6为1,2,4,6,5,3,求它的下一 个排列 解:1求m:4,6是最右的顺序,an=4, m=3 2定义b:b1=1,b2=2,在am右边 还有6,5,3,其中6和5大于am=4, 5是最小的,b3=5 3余下a3=4,a4=6,a6=3,从小 到大排起来,为3,4,6,即让b4=3, b==4, b 6 6 得到1,2,4,6,5,3的下一个排 列:1,2,5,3,4,6 2/24/202111:38PM Deren Chen, Zhejiang Univ
计数原理 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 5 例１：设有ｎ＝６个数字的排列ａ1，ａ2，…， ａ6为１，２，４，６，５，３，求它的下一 个排列。 解：1.求m： ４，６是最右的顺序，ａm＝４， ｍ＝３ 2.定义bi： ｂ1＝１，ｂ2＝２，在ａm右边 还有６，５，３，其中６和５大于ａm＝４， ５是最小的，ｂ3＝５ 3.余下ａ3＝４，ａ4＝６，ａ6＝３，从小 到大排起来，为３，４，６，即让ｂ4＝３， ｂ5＝４，ｂ6＝６ 得到１，２，４，６，５，３的下一个排 列：１，２，５，３，４，６