资源描述
5/20/20201:42AM,DerenChen,ZhejiangUniv.,1,4、计数原理/Counting4.5排列与组合的生成GeneratingPermutationsandCombinations,5/20/20201:42AM,DerenChen,ZhejiangUniv.,2,在实际应用中，往往不仅需要计数，而且要把各种情况都枚举出来。,一、字典序排列/lexicographicorderingforpermutation定义:顺序：排列1，2，n中相邻两数ii+1，称为一个顺序。逆序：排列1，2，n中相邻两数ii+1，称为一个逆序。,5/20/20201:42AM,DerenChen,ZhejiangUniv.,3,例：排列顺序：，逆序：，。对个对象进行全排列，有！个排列，可以对个对象加上标记。不失一般性，我们只需对个自然数，进行全排列，枚举出所有的情况。,字典序排列算法给出初始排列：1，若k已定义(！）k1，2，m，n,5/20/20201:42AM,DerenChen,ZhejiangUniv.,4,则按下列规定，定义k的下一个排列k+11，2，m，n(1)寻找m：|jj+1即m，m+1是最右面的顺序，自m+1开始均为逆序。(2)给出i（，）第项之前的项不变：11，22，m-1m-1）mp|pm，）即在m右面大于m的项中选取最小的项作为m。）把m，m+1，p-1，p+1，n从小到大排列，送入m+1，m+2，n。,5/20/20201:42AM,DerenChen,ZhejiangUniv.,5,例：设有个数字的排列1，2，6为，求它的下一个排列。,解：1.求m：，是最右的顺序，m，2.定义bi：1，2，在m右边还有，其中和大于m，是最小的，33.余下3，4，6，从小到大排起来，为，即让4，5，6得到，的下一个排列：，。,5/20/20201:42AM,DerenChen,ZhejiangUniv.,6,例：求时，的所有排列。,解：2,5/20/20201:42AM,DerenChen,ZhejiangUniv.,7,定理一：用字典序排序方法可由，的第一个排列，（全顺序）开始，得到！个排列，且最后一个排列是，（全逆序）。,注：例中开始的排列与结束时的排列的特征，可用数学归纳法证明，对任意个数用此算法都能枚举出所有的排列。,5/20/20201:42AM,DerenChen,ZhejiangUniv.,8,二、字典序组合/lexicographicorderingforcombination,5/20/20201:42AM,DerenChen,ZhejiangUniv.,9,字典序组合算法:1，若i1，2，k已得到（Cnk）则构造下一个子集i+11，2，k(1)|j（），即1，2，j，k与，（），比较从右边开始比较第一个不相等的项为m,5/20/20201:42AM,DerenChen,ZhejiangUniv.,10,(2)构造i+1）11，22，m-1m-1）mm+1）m+1m+1,m+2m+1，kk-1,注：不用耽心k会取到大于的数,5/20/20201:42AM,DerenChen,ZhejiangUniv.,11,例：，。若，则（1，2，3，4，5，6，7）与（，）比较由于，据算法，5不会取到，只能小于，于是mm至多是，6，7至多是和，不会取到大于的数。,例:求，的子集，共有C106个，当i，时，求i+1。,5/20/20201:42AM,DerenChen,ZhejiangUniv.,12,i，与，比较，m，于是11，22，33，44，5-，6得i+1，,继续求：i+2，i+3，i+4，i+5，,5/20/20201:42AM,DerenChen,ZhejiangUniv.,13,5/20/20201:42AM,DerenChen,ZhejiangUniv.,14,练习,pp.3005、10,
展开阅读全文