计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,1
4、计数原理 /Counting
4.5 排列与组合的生成
Generating Permutations
and Combinations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,2
在实际应用中,往往不仅需要计数,而且要把各种情况都枚举出来 。
一,字典序排列 /lexicographic ordering
for permutation
定义,
顺序：排列ａ 1,ａ 2,…,ａ n中相邻两数
ａ i＜ａ i+1,称为一个顺序 。
逆序：排列ａ 1,ａ 2,…,ａ n中相邻两数
ａ i＞ａ i+1,称为一个逆序 。
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,3
例：
排列１ ３ ２ ６ ５ ４
顺序：１３,２６,逆序：３２,６５,５４ 。
对ｎ个对象进行全排列,有ｎ ！ 个排列,可以对ｎ个对象加上标记 。
不失一般性,我们只需对ｎ个自然数 ｛ １,
２,…,ｎ ｝ 进行全排列,枚举出所有的情况 。
１,给出初始排列：ｐ 1＝１,２,３,４,…,ｎ
２,若ｐ k已定义 (１ ≤ ｋ ≤ ｎ ！ －１ ）
ｐ k＝ａ 1,ａ 2,…,ａ m,…,ａ n
计数原理
7/31/2009 11:29 AM 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。
计数原理
7/31/2009 11:29 AM 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＝６
得到１,２,４,６,５,３的下一个排列：１,２,５,３,４,６ 。
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,6
例２：求ｎ＝４时 ｛ １,２,３,４ ｝ 的所有排列 。
解：
１２３４ → １２４３ → １３２４ → １３４ 2→ １
４２３ → １４３２ → ２１３４ → ２１４３ → ２
３１４ → ２３４１ → ２４１３ → ２４３１ → ３
１２４ → ３１４２ → ３２１４ → ３２４１ → ３
４１２ → ３４２１ → ４１２３ → ４１３２ → ４
２１３ → ４２３１ → ４３１２ → ４３２１
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,7
定理一：
用字典序排序方法可由１,２,３,…，
ｎ的第一个排列１,２,…,ｎ （ 全顺序 ） 开始,得到ｎ ！ 个排列,且最后一个排列是ｎ,
ｎ－１,…,２,１ （ 全逆序 ） 。
注：
例２中开始的排列与结束时的排列的特征,
可用数学归纳法证明,对任意ｎ个数用此算法都能枚举出所有的排列 。
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,8
二,字典序组合 /lexicographic ordering for
combination
对任意ｎ个对象，求取其中ｋ个对象组合的所有组合。
不失一般性，只要讨论求 ｛１，２，…，ｎ｝的所有ｋ子集，共
k
n
C 个。
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,9
字典序组合算法,
１,Ｓ 1＝ ｛ １,２,…,ｋ ｝
２,若Ｓ i＝ ｛ ａ 1,ａ 2,…,ａ k｝ 已得到
（ １ ≤ ｉ ≤ Cnk －１ ） 则构造下一个子集
Ｓ i+1＝ ｛ ｂ 1,ｂ 2,…,ｂ k｝
(1)ｍ＝ｍａｘ {ｊ |ａ j≠ ｎ－ （ ｋ－ｊ ） }，
即 ｛ ａ 1,ａ 2,…ａ j,…,ａ k｝ 与
｛ ｎ－ｋ＋１,ｎ－ｋ＋２,…，
ｎ－ｋ＋ｊ,…,（ ｎ－１ ）,ｎ ｝ 比较从右边开始比较第一个不相等的项为ａ m
计数原理
7/31/2009 11:29 AM 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会取到大于ｎ的数计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,11
例：
ｎ＝１０,ｋ＝７ 。 若ｍ＝５,则
（ ａ 1,ａ 2,ａ 3,ａ 4,ａ 5,ａ 6,ａ 7）
与 （ ４,５,６,７,８,９,１０ ） 比较由于ｍ＝５,据算法,ａ 5不会取到８,
只能小于８,于是ｂ m＝ａ m＋１至多是８,
ａ 6,ａ 7至多是９和１０,不会取到大于１
０的数 。
例３,求 ｛ １,２,…,１０ ｝ 的６子集,共有 C106＝２１０个,当Ｓ i＝ ｛ ２,３,５,６,
９,１０ ｝ 时,求Ｓ i+1。
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,12
Ｓ i＝ ｛ ２,３,５,６,９,１０ ｝
与 ｛ ５,６,７,８,９,１０ ｝ 比较
６ ≠ ８,ａ m＝６,ｍ＝４,
于是ｂ 1＝ａ 1＝２,ｂ 2＝ａ 2＝３,ｂ 3＝ａ 3＝５,
ｂ 4＝ａ 4＋１＝７,ｂ 5-７＋１＝８,
ｂ 6＝８＋１＝９
得Ｓ i+1＝ ｛ ２,３,５,７,８,９ ｝
Ｓ i+2
Ｓ i+3
Ｓ i+4
Ｓ i+5
……
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,13
定理二：
对ｎ个元素的ｋ子集组合，用字典序组合法，
可由 ｛１，２，…，ｋ｝开始，到 ｛ｎ－ｋ＋１，ｎ
－ｋ＋２，…，ｎ－１，ｎ｝结束，共有
k
n
C 个组合。
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,14
练 习
pp.300 5,10
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,1
4、计数原理 /Counting
4.5 排列与组合的生成
Generating Permutations
and Combinations
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,2
在实际应用中,往往不仅需要计数,而且要把各种情况都枚举出来 。
一,字典序排列 /lexicographic ordering
for permutation
定义,
顺序：排列ａ 1,ａ 2,…,ａ n中相邻两数
ａ i＜ａ i+1,称为一个顺序 。
逆序：排列ａ 1,ａ 2,…,ａ n中相邻两数
ａ i＞ａ i+1,称为一个逆序 。
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,3
例：
排列１ ３ ２ ６ ５ ４
顺序：１３,２６,逆序：３２,６５,５４ 。
对ｎ个对象进行全排列,有ｎ ！ 个排列,可以对ｎ个对象加上标记 。
不失一般性,我们只需对ｎ个自然数 ｛ １,
２,…,ｎ ｝ 进行全排列,枚举出所有的情况 。
１,给出初始排列：ｐ 1＝１,２,３,４,…,ｎ
２,若ｐ k已定义 (１ ≤ ｋ ≤ ｎ ！ －１ ）
ｐ k＝ａ 1,ａ 2,…,ａ m,…,ａ n
计数原理
7/31/2009 11:29 AM 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。
计数原理
7/31/2009 11:29 AM 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＝６
得到１,２,４,６,５,３的下一个排列：１,２,５,３,４,６ 。
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,6
例２：求ｎ＝４时 ｛ １,２,３,４ ｝ 的所有排列 。
解：
１２３４ → １２４３ → １３２４ → １３４ 2→ １
４２３ → １４３２ → ２１３４ → ２１４３ → ２
３１４ → ２３４１ → ２４１３ → ２４３１ → ３
１２４ → ３１４２ → ３２１４ → ３２４１ → ３
４１２ → ３４２１ → ４１２３ → ４１３２ → ４
２１３ → ４２３１ → ４３１２ → ４３２１
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,7
定理一：
用字典序排序方法可由１,２,３,…，
ｎ的第一个排列１,２,…,ｎ （ 全顺序 ） 开始,得到ｎ ！ 个排列,且最后一个排列是ｎ,
ｎ－１,…,２,１ （ 全逆序 ） 。
注：
例２中开始的排列与结束时的排列的特征,
可用数学归纳法证明,对任意ｎ个数用此算法都能枚举出所有的排列 。
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,8
二,字典序组合 /lexicographic ordering for
combination
对任意ｎ个对象，求取其中ｋ个对象组合的所有组合。
不失一般性，只要讨论求 ｛１，２，…，ｎ｝的所有ｋ子集，共
k
n
C 个。
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,9
字典序组合算法,
１,Ｓ 1＝ ｛ １,２,…,ｋ ｝
２,若Ｓ i＝ ｛ ａ 1,ａ 2,…,ａ k｝ 已得到
（ １ ≤ ｉ ≤ Cnk －１ ） 则构造下一个子集
Ｓ i+1＝ ｛ ｂ 1,ｂ 2,…,ｂ k｝
(1)ｍ＝ｍａｘ {ｊ |ａ j≠ ｎ－ （ ｋ－ｊ ） }，
即 ｛ ａ 1,ａ 2,…ａ j,…,ａ k｝ 与
｛ ｎ－ｋ＋１,ｎ－ｋ＋２,…，
ｎ－ｋ＋ｊ,…,（ ｎ－１ ）,ｎ ｝ 比较从右边开始比较第一个不相等的项为ａ m
计数原理
7/31/2009 11:29 AM 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会取到大于ｎ的数计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,11
例：
ｎ＝１０,ｋ＝７ 。 若ｍ＝５,则
（ ａ 1,ａ 2,ａ 3,ａ 4,ａ 5,ａ 6,ａ 7）
与 （ ４,５,６,７,８,９,１０ ） 比较由于ｍ＝５,据算法,ａ 5不会取到８,
只能小于８,于是ｂ m＝ａ m＋１至多是８,
ａ 6,ａ 7至多是９和１０,不会取到大于１
０的数 。
例３,求 ｛ １,２,…,１０ ｝ 的６子集,共有 C106＝２１０个,当Ｓ i＝ ｛ ２,３,５,６,
９,１０ ｝ 时,求Ｓ i+1。
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,12
Ｓ i＝ ｛ ２,３,５,６,９,１０ ｝
与 ｛ ５,６,７,８,９,１０ ｝ 比较
６ ≠ ８,ａ m＝６,ｍ＝４,
于是ｂ 1＝ａ 1＝２,ｂ 2＝ａ 2＝３,ｂ 3＝ａ 3＝５,
ｂ 4＝ａ 4＋１＝７,ｂ 5-７＋１＝８,
ｂ 6＝８＋１＝９
得Ｓ i+1＝ ｛ ２,３,５,７,８,９ ｝
Ｓ i+2
Ｓ i+3
Ｓ i+4
Ｓ i+5
……
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,13
定理二：
对ｎ个元素的ｋ子集组合，用字典序组合法，
可由 ｛１，２，…，ｋ｝开始，到 ｛ｎ－ｋ＋１，ｎ
－ｋ＋２，…，ｎ－１，ｎ｝结束，共有
k
n
C 个组合。
计数原理
7/31/2009 11:29 AM Deren Chen,Zhejiang Univ,14
练 习
pp.300 5,10
