计数原 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;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|aam, 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＝６ 得到１，２，４，６，５，３的下一个排 列：１，２，５，３，４，６
计数 例2:求n=4时{1,2,3,4}的所有 排列。 解: 1234→1243→1324→1342→1 423→1432→2134→2143→2 314→2341→2413→2431→3 124→3142→3214→3241→3 412→3421→4123→4132→4 213→4231→4312→4321 2/24/202111:38PM Deren Chen, Zhejiang Univ
计数原理 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 6 例２：求ｎ＝４时｛１，２，３，４｝的所有 排列。 解： １２３４→１２４３→１３２４→１３４2→１ ４２３→１４３２→２１３４→２１４３→２ ３１４→２３４１→２４１３→２４３１→３ １２４→３１４２→３２１４→３２４１→３ ４１２→３４２１→４１２３→４１３２→４ ２１３→４２３１→４３１２→４３２１
计数原 例2中开始的排列与结束时的排列的特征, 可用数学归纳法证明,对任意n个数用此算法 都能枚举出所有的排列。 定理一: 用字典序排序方法可由1,2,3 n的第一个排列1,2,,n(全顺序)开 始,得到n!个排列,且最后一个排列是n, n-1,…,2,1(全逆序)。 2/24/202111:38PM Deren Chen, Zhejiang Univ 7
计数原理 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 7 定理一： 用字典序排序方法可由１，２，３，…， ｎ的第一个排列１，２，…，ｎ（全顺序）开 始，得到ｎ！个排列，且最后一个排列是ｎ， ｎ－１，…，２，１（全逆序）。 注： 例２中开始的排列与结束时的排列的特征， 可用数学归纳法证明，对任意ｎ个数用此算法 都能枚举出所有的排列
计数原理 二、字典序组合/1 lexicographic ordering for combination 对任意n个对象,求取其中k个对象组合的所有 组合。 不失一般性,只要讨论求{1,2,…,n}的 所有k子集,共CA个 2/24/202111:38PM Deren Chen, Zhejiang Univ 8
计数原理 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 8 二 、 字典序组合 /lexicographic ordering for combination 对任意ｎ个对象，求取其中ｋ个对象组合的所有 组合。 不失一般性，只要讨论求｛１，２，…，ｎ｝的 所有ｋ子集，共 k Cn 个
计数原 字典序组合算法: 1.S1={1,2,…,k 2.若S1={a1,a2,…,ak}已得到 (1≤i≤Ck-1)则构造下一个子集 {b1,b (1)m=max{ja;≠n-(k一j)}, 即{a1,a2,…aj,…,ak}与 {n-k+1,n-k+2 n-k+j,…,(n-1),n}比较 从右边开始比较第一个不相等的项为am 2/24/202111:38PM Deren Chen, Zhejiang Univ 9
计数原理 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 9 字典序组合算法: １．Ｓ1 ＝｛１，２，…，ｋ｝ ２．若Ｓi ＝｛ａ1，ａ2，…，ａk｝已得到 （１≤ｉ≤Cn k －１）则构造下一个子集 Ｓi+1 ＝｛ｂ1，ｂ2，…，ｂk｝ (1)ｍ＝ｍａｘ{ｊ|ａj≠ｎ－（ｋ－ｊ）}， 即｛ａ1，ａ2，…ａj，…，ａk｝与 ｛ｎ－ｋ＋１，ｎ－ｋ＋２，…， ｎ－ｋ＋ｊ，…，（ｎ－１） ，ｎ｝比较 从右边开始比较第一个不相等的项为ａm
计数原 (2)构造S+1 a a 1 b a 2, a b)b=a+ c) bm+1=bm+l, bm+2=b+1t 1 b=b-1+1 注: 不用耽心b会取到大于n的数 2/24/202111:38PM Deren Chen, Zhejiang Univ 10
计数原理 2/24/2021 11:38 PM Deren Chen, Zhejiang Univ. 10 (2)构造Ｓi+1 ａ）ｂ1＝ａ1，ｂ2＝ａ2，…，ｂm-1＝ａm-1 ｂ）ｂm＝ａm +1 ｃ）ｂm+1＝ｂm +1,ｂm+2＝ｂm+1＋１，…， ｂk＝ｂk-1＋１ 注： 不用耽心ｂk会取到大于ｎ的数
