《排列与组合的生成》PPT课件.ppt

《《排列与组合的生成》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4、计数原理/Counting4.5排列与组合的生成GeneratingPermutationsandCombinations7/25/20211DerenChen,ZhejiangUniv.在实际应用中，往往不仅需要计数，而且要把各种情况都枚举出来。一、字典序排列/lexicographicorderingforpermutation定义:顺序：排列ａ1，ａ2，…，ａn中相邻两数ａi＜ａi+1，称为一个顺序。逆序：排列ａ1，ａ2，…，ａn中相邻两数ａi＞ａi+1，称为一个逆序。7/25/20212DerenChen,ZhejiangUniv.例：排列１

2、３２６５４顺序：１３，２６，逆序：３２，６５，５４。对ｎ个对象进行全排列，有ｎ！个排列，可以对ｎ个对象加上标记。不失一般性，我们只需对ｎ个自然数｛１，２，…，ｎ｝进行全排列，枚举出所有的情况。字典序排列算法１．给出初始排列：ｐ1＝１，２，３，４，…，ｎ２．若ｐk已定义(１≤ｋ≤ｎ！－１）ｐk＝ａ1，ａ2，…，ａm，…，ａn7/25/20213DerenChen,ZhejiangUniv.则按下列规定，定义ｐk的下一个排列ｐk+1＝ｂ1，ｂ2，…，ｂm，…，ｂn(1)寻找ａm：ｍ＝ｍａｘ{ｊ

3、ａj＜ａj+1}即ａm，ａm+1是最右面的顺序，自ａm+

4、1开始均为逆序。(2)给出ｂi（ｉ＝１，２，…，ｎ）ａ）第ｍ项之前的项不变：ｂ1＝ａ1，ｂ2＝ａ2，…，ｂm-1＝ａm-1ｂ）ｂm＝ｍｉｎ{ａp

5、ａp＞ａm，ｐ＞ｍ）即在ａm右面大于ａm的项中选取最小的项作为ｂm。ｃ）把ａm，ａm+1，…，ａp-1，ａp+1，…，ａn从小到大排列，送入ｂm+1，ｂm+2，…，ｂn。7/25/20214DerenChen,ZhejiangUniv.例１：设有ｎ＝６个数字的排列ａ1，ａ2，…，ａ6为１，２，４，６，５，３，求它的下一个排列。解：1.求m：４，６是最右的顺序，ａm＝４，ｍ＝３2.定义bi：ｂ1＝１，ｂ2＝

6、２，在ａm右边还有６，５，３，其中６和５大于ａm＝４，５是最小的，ｂ3＝５3.余下ａ3＝４，ａ4＝６，ａ6＝３，从小到大排起来，为３，４，６，即让ｂ4＝３，ｂ5＝４，ｂ6＝６得到１，２，４，６，５，３的下一个排列：１，２，５，３，４，６。7/25/20215DerenChen,ZhejiangUniv.例２：求ｎ＝４时｛１，２，３，４｝的所有排列。解：１２３４→１２４３→１３２４→１３４2→１４２３→１４３２→２１３４→２１４３→２３１４→２３４１→２４１３→２４３１→３１２４→３１４２→３２１４→３２４１→３４１２→３４２１→４１２３→４１３２→４２１

7、３→４２３１→４３１２→４３２１7/25/20216DerenChen,ZhejiangUniv.定理一：用字典序排序方法可由１，２，３，…，ｎ的第一个排列１，２，…，ｎ（全顺序）开始，得到ｎ！个排列，且最后一个排列是ｎ，ｎ－１，…，２，１（全逆序）。注：例２中开始的排列与结束时的排列的特征，可用数学归纳法证明，对任意ｎ个数用此算法都能枚举出所有的排列。7/25/20217DerenChen,ZhejiangUniv.二、字典序组合/lexicographicorderingforcombination7/25/20218DerenChen,Zhejian

8、gUniv.字典序组合算法:１．Ｓ1＝｛１，２，…，ｋ｝２．若Ｓi＝｛ａ1，ａ2，…，ａk｝已得到（１≤ｉ≤Cnk－１）则构造下一个子集Ｓi+1＝｛ｂ1，ｂ2，…，ｂk｝(1)ｍ＝ｍａｘ{ｊ

9、ａj≠ｎ－（ｋ－ｊ）}，即｛ａ1，ａ2，…ａj，…，ａk｝与｛ｎ－ｋ＋１，ｎ－ｋ＋２，…，ｎ－ｋ＋ｊ，…，（ｎ－１），ｎ｝比较从右边开始比较第一个不相等的项为ａm7/25/20219DerenChen,ZhejiangUniv.(2)构造Ｓi+1ａ）ｂ1＝ａ1，ｂ2＝ａ2，…，ｂm-1＝ａm-1ｂ）ｂm＝ａm+1ｃ）ｂm+1＝ｂm+1,ｂm+2＝ｂm+1＋１

10、，…，ｂk＝ｂk-1＋１注：不用耽心ｂk会取到大于ｎ的数7/25/202110DerenChen,ZhejiangUniv.例：ｎ＝１０，ｋ＝７。若ｍ＝５，则（ａ1，ａ2，ａ3，ａ4，ａ5，ａ6，ａ7）与（４，５，６，７，８，９，１０）比较由于ｍ＝５，据算法，ａ5不会取到８，只能小于８，于是ｂm＝ａm＋１至多是８，ａ6，ａ7至多是９和１０，不会取到大于１０的数。例３:求｛１，２，…，１０｝的６子集，共有C106＝２１０个，当Ｓi＝｛２，３，５，６，９，１０｝时，求Ｓi+1。7/25/202111DerenChen,ZhejiangUniv.Ｓi＝｛２，３，５

11、，６，９，１０｝与｛５，６，７，８，９，１０｝比较６