2
以A以字典序先于B。即拿不同的元素比较大小。
组合中的元素本身是无序的，但为了方便 讨论，我们规定{1, 2, …, n}中的任一r-组合
均按字典序书写成如下“单词”的形式：
a1a2…ar 其中a1<a2<…<ar
特别是书写成 “单词”形式中不允许由
相同的元素重复出现。 回到前个例子：从{1,2,3,4}中选出2-组合中 2 3
23
一个二元组的形式，就是序偶。 例如：集合A={a,b} 和B={1,2,3}, 如果规定A
集合的元素作为第一坐标，B集合的元素作为
第二坐标，那么它们可以构成下列序偶： <a,1>, <a,2>,<a,3>,<b,1>,<b,2>,<b,3> 笛卡儿积------两个集合A，B作下列运算： A×B={< ai, bj > ai A, bj B } 得到全部序偶。
8
根据上述定理，我们可以描述生成{1, 2, …, n} 的字典序r-组合的算法如下：
1. 输出正整数n，r，并且r ≤ n；
2. 构造{1, 2, …, n}的字典序的第一个r-组 合a1a2…ar ＝1 2…r，并输出； 3. 当a1a2…ar ≠ (n-r+1)(n- r+2)…n时，做 ⅰ) 确定最大的整数k，使得ak＋1 ≤ n且ak
n a r 1 n a r 2 1
证明：i) 从a1a2…ar 的第一位字符a1开始分析，a1
后面肯定存在比a1大的数： (a1+1), (a1+2),……
18
n a1 共n－a1个, 以它们作为第一为字符r-组合有 r 个。 保持第一个字符a1不变，对第二个字
输出：以升序列出{1,2,…,n}的所有r组合。 1.procedure combination(r,n) 2. for i:=1 to r do 3. si=i 4. print s1,…,sr //打印第一个r组合 5. for i:=2 to c(n, r) do
13
6. begin
7. m:=r
符a2进行分析：
n a 2 ii)在a1a2…ar 后面存在从a2开始增大的 r 1 个r-组合，其中固定了第一个元素是a1，这样
的实际变化的组合是(r-1)-组合，第二个元素 大于a2。
……..
19
r-1) 在a1a2…ar 后面存在从第ar-1个元素开始增大
7
例如 S＝ {1, 2, 3, 4, 5, 6}， a1a2 a3a4＝1456是S的 一个4-组合，对于该组合来讲，k＝4时
ak＝6； k＝3时ak＝5<6，但ak＋1＝6已在该组
合之中；当k＝2时ak＝4 <6 ，但ak＋1＝5也在
该组合之中； k＝1时ak＝1<6，并且ak＋1＝2
不在该组合中。于是k＝1是我们求得的最大 整数，因此，1456的直接后继4-组合是 (ak+1)(ak+2) (ak+3)(ak+4-1+1)，即： 2345
第四章 生成排列和组合
4.4 生成r-组合
前面我们讨论了逐次性法则生成一个集合
的所有组合的算法。本次课我们将讨论n个元
素的集合中取出r个元素的组合算法；这就如同
“陕西风采”33选7的彩票选号方案。
例：从{1,2,3,4}中选出2-组合:
(1,2), (1,3), (2,3), (1,4) ,(2,4) ,(3,4) 。
= 22。
21
2467的位置：
8 8 2 8 4 8 6 8 7 8 6 4 2 1 4 4 4 1 4 2 4 3 4 4 3 2 1
＋1 不在a1a2…ar 之中；
9
ⅱ) 构造r-组合 a1a2…ak－1 (ak+1)(ak+2)… (ak+r-k+1)
作为新的r-组合a1a2…ar ；
ⅲ) 输出r-组合a1a2…ar ； 这里有一个用 C++编写的求 r-组合的程序，提 供给大家参考：
10
产生字典序r-组合的程序 此算法以升序列出{1,2,…8}的所有4-组合。 以下用C++程序编写。 # include <fstream. h>
{ h[0] = a[s] ;h[1] = a[t]; h[2] = a[u];
h[3] = a[v]
for (int q =0 ;q ＜4;q++)
myf <<h[q]<<― ―;
myf<<end;}}
结束
12
产生字典序r-组合的程序 此算法以升序列出{1,2,…,n}的所有r-组合。
输入：r，n
8 8 1 8 2 8 5 8 8 8 7 6 3 0 4 4 4 1 4 2 4 3 4 4 3 2 1
的前后组合是：1 4和2 4。下面说的组合都有序
3
例：考虑{1,2,3,4,5,6,7}的5-组合被列出的顺序。 第一个组合是12345，接下来是12346和12347。
下面是12356和12357。最后一个组合是34567。
（第一个组合）1, 2, | 3, 4, 5, | 6,7 （最后一个组合）
1
设集合S={1, 2, 3, …, n}，于是S中的元素存 在一种自然顺序1< 2<…< n 。如果A，B是S
的两个r-组合(子集)，且在集合A∪B－A∩B中
(即：在其中一个集合中而不在两个集合中)的最
小元素属于A，则称组合A以字典序先于B。
例:集合{1,2,3,4}的两个组合A={1,2,3};B={2,3,4}, 它们中不同的元素是1和4,其中1小,而且在A中,所
定理4.4.1设a1a2…ar 是{1, 2, …, n}的一个r-组合。 在字典 顺序中，第一个r-组合是123…r；
最后一个r-组合是 (n-r+1)(n-r+2) …n 。如果
a1a2…ar ≠ (n-r+1)(n- r+2)…n，则a1a2…ar 的直
接后继r-组合是：
a1a2…ak－1 (ak+1)(ak+2)… (ak+r-k+1) 其中，k是满足ak<n且ak＋1不在a1, a2,…, ar中的最 大整数, 即从ak开始改变字符，按加1方式。
出2367后面的组合。
没有以23开始的X的4-组合排在2367之后。
于是2367后面的组合必然是以24开始。因为 2456是以24开始的描述X的4-组合的最小组合， 则答案是2456。 (为何不可以是2413？)
5
由于所有组合都安定了由小到大的顺序，我们寻 找的后一个组合一定大于前一个。
可建立一个模式。给出一个字符串α=a1…ar ，
n a r 1 个r-组合，它们都从a1a2…ar-2开始， 2
第(r-1)个元素大于原来的ar-1，这样的实际变化
的组合是2-组合。
n ar r ቤተ መጻሕፍቲ ባይዱ在a1a2…ar 后面存在 个r-组合，它们都 1 从a1a2…ar-1开始，但第r个元素大于ar，这样的
# include <iomanip. h>
const n=8
main c
Int a[n]={1,2,…8}
Int h[4]={0} Int s,t,u,v
11
Ofstream myf (―c://out.txt); for (s = 0; s＜＝n - 4;s++); { for (t=s+1; t ＜＝n – 3;t++) for (u=t+1; u ＜＝n – 2 ;u++) for (v=u+1; v ＜＝n – 1 ;v++)
例：当我们列出X={1,2,3,4,5,6,7}的-5组合时，找
出13467后面的组合。 没有以134开始的的5-组合的字符串排在
13467之后。于是13467后面的组合必然是以
4
135开始。因为13567是以135开始的描述X的5- 组 合的最小组合，则答案就是13567。
例：当我们列出X={1,2,3,4,5,6,7}的4-组合时，找
2 3 4 再进行全排列
234 243
312
321
412
421
413
431
423
432
231
213
241
214
341
314
342
324
17
关于每一个r-组合的位置 定理4.4.2 {1,2,….n}的r-组合a1a2…ar 出现
在{1,2,….n}的r-组合的字典序中的位置如下：
n n a1 n a 2 r r r 1 .....
8.
9.
max_val:=n
while sm= max_val do
10.
11. 12. 13. 14.
// 找到不是最大值的最右元素sm
begin m:=m-1 max_val:= max_val-1 end
14
15. // 最右元素增一
16. 18.