LG#P1157. 组合的输出

组合的输出

P1157 组合的输出

题目描述

\hspace{15pt}组合是从 nn 个元素中抽出 rr 个元素(不分顺序,且 r≦nr \leqq n)。我们可以简单地把 nn 个元素理解为自然数 1,2,…,n1,2,\dots,n,从中任取 rr 个数。

\hspace{15pt}给定 nn 和 rr,请你按字典序输出从 1∼n1 \sim n 中取出 rr 个数的全部组合。同一个组合内部的元素按从小到大排列。

∙ \hspace{15pt}\bullet\,组合:从 nn 个元素中选出 rr 个元素且不考虑顺序,得到的一个组合。例如 n=5,r=3n=5,r=3 时,{1,2,5}\{1,2,5\} 与 {1,5,2}\{1,5,2\} 是同一个组合。

∙ \hspace{15pt}\bullet\,字典序:从两个序列的第一个元素开始逐个比较,直到找到第一个不同的位置,通过比较这个位置元素的大小得出两个序列的大小,称为字典序比较。

输入格式

\hspace{15pt}输入一行两个整数 $n, r \left(1 \leqq n \leqq 20;\ 1 \leqq r \leqq n\right)$,分别代表元素的总数和每个组合包含的元素个数。

输出格式

\hspace{15pt}共输出 (nr)\binom{n}{r} 行,每行一个组合,其中的元素按从小到大排列,所有组合按字典序排列。

\hspace{15pt}每个数字占 33 个字符的位置,即在输出该数字之前补足空格,使其总宽度为 33。

测试样例

5 3
  1  2  3
  1  2  4
  1  2  5
  1  3  4
  1  3  5
  1  4  5
  2  3  4
  2  3  5
  2  4  5
  3  4  5

样例 1 解释

\hspace{15pt}从 1∼51 \sim 5 中选出 33 个数,共有 (53)=10\binom{5}{3} = 10 个组合。按字典序排列时先比较第一个数,第一个数相同时再比较第二个数,依此类推,因此以 11 开头的 66 个组合排在最前面,其内部按第二个数 2,3,42,3,4 分组。

\hspace{15pt}注意每个数字之前都补了空格:一位数前面有 22 个空格,使其总宽度为 33。

4 2
  1  2
  1  3
  1  4
  2  3
  2  4
  3  4

样例 2 解释

\hspace{15pt}从 1∼41 \sim 4 中选出 22 个数,共有 (42)=6\binom{4}{2} = 6 个组合,按字典序依次是 {1,2},{1,3},{1,4},{2,3},{2,4},{3,4}\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}。

提示

\hspace{15pt}对于 100%100\% 的数据,1≦n≦201 \leqq n \leqq 20,1≦r≦n1 \leqq r \leqq n。

\hspace{15pt}组合的个数为 (nr)\binom{n}{r},当 n=20,r=10n = 20, r = 10 时共有 1.84756×1051.84756 \times 10^5 行,可以用回溯法按字典序依次生成。

\hspace{15pt}如果你想使用 setw 控制场宽,需要包含头文件 <iomanip>。