P1157 组合的输出
题目
排列与组合是常用的数学方法，其中组合就是从 \(n\) 个元素中抽出 \(r\) 个元素（不分顺序且 \(r \le n\)），我们可以简单地将 \(n\) 个元素理解为自然数 \(1,2,\ldots,n\)，从中任取 \(r\) 个数。
现要求你输出所有组合。
例如 \(n=5,r=3\)，所有组合为：
\(123,124,125,134,135,145,234,235,245,345\)。
输入
一行两个自然数 \(n,r(1<n<21,0 \le r \le n)\)。
输出
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
注意哦！输出时，每个数字需要 \(3\) 个场宽。以 C++ 为例，你可以使用下列代码：
cout << setw(3) << x;
输出占 \(3\) 个场宽的数 \(x\)。注意你需要头文件 iomanip。
样例
输入
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
思路一
我们构造一个 \(n\) 位的二进制数，二进制数的第 \(i\) 位代表第 \(i\) 个元素的选取状态。枚举全集 \(\lbrack 0,2^n-1 \rbrack\) 共 \(2^n\) 种状态，代码为
for (int S = 0; S <= (1 << n) - 1; S ++ )
其中 1 << n 表示二进制数 \(1\) 向左移 \(n\) 位，即十进制数 \(2^n\)，(1 << n) - 1 是由 \(n\) 个 \(1\) 构成的二进制数。二进制数从右向左依次为第 \(0\) 位，第 \(1\) 位，\(\cdots\)，第 \(n - 1\) 位，分别表示每个位置对应的元素的选取状态，如果该位置为 \(1\)，表示对应位置的元素被选取，如果为 \(0\)，表示没有被选取。若某个状态 \(S(S\) 有 \(n\) 位 \()\) 的二进制数含有 \(r\) 个 \(1\)，那么它二进制为 \(1\) 的位对应的元素就是我们要选取的。
如何判断 \(S\) 中某一位是否为 \(1\) 呢？可以借助 \(1\) 左移 \(i\) 位得到的二进制数与 \(S\) 进行“\(\&\)”运算，如果结果为正数，则第 \(i\) 位为 \(1\)。例如：“\(S=10000100,S \& (1<<2)=00000100\)”，则说明 \(S\) 中第 \(2\) 位为 \(1\)，表示题意中第 \(n-i\) 个元素要被选取。
代码
#include <bits/stdc++.h>
using namespace std;
int a[30], n, r, cnt;
int main()
{
cin >> n >> r;
for (int S = (1 << n) - 1; S >= 0; S -- )
{
cnt = 0;
for (int i = 0; i < n; i ++ )
{
if (S & (1 << i))
a[cnt ++] = i;
}
if (cnt == r)
{
for (int i = r - 1; i >= 0; i -- )
printf("%3d", n - a[i]);
cout << '\n';
}
}
return 0;
}
思路二
题目从 \(n\) 个数中选 \(r\) 个数字的组合，且 \(n\) 小于 \(21\)，我们构造一个 \(n\) 位的二进制数，二进制数的第 \(i\) 位代表第 \(i\) 个元素的选取状态，与前面的方法相同。如果 __builtin_popcount(x) 函数等于 \(r\)，则说明二进制数 \(x\) 含有 \(r\) 个 \(1\)，是题目需要的状态。可以对 \(x\) 进行数位分离，将数字为 \(1\) 的位置用数组储存下来，分离结束后按要求输出 \(x\) 中每个 \(1\) 的位置。
这道题需要注意的是输出格式，要求按照字典序输出。因此不能从小到大枚举二进制数，例如“\(01101\)”这个二进制数表示第 \(1,3,4\) 个数字被选择。“\(10011\)”这个二进制数表示第 \(1,2,5\) 个数字被选择。而二进制数“\(01101\)”\(<\)“\(10011\)”，因此“\(1,3,4\)”这种状态会先被枚举到，但“\(1,2,5\)”的字典序小于“\(1,3,4\)”。因此为了让“\(1\)”尽可能靠前出现以满足字典序要求，我们可以将状态从大到小枚举。
代码
#include <bits/stdc++.h>
using namespace std;
int n, r, cnt, a[50], S, x, p;
int main()
{
cin >> n >> r;
S = (1 << n) - 1;
for (int i = S; i >= 0; i -- )
{
cnt = 0;
if (__builtin_popcount(i) == r)
{
x = i;
p = 1;
while (x)
{
if (x & 1)
a[++ cnt] = n - p + 1;
x >>= 1;
p ++;
}
for (int j = cnt; j >= 1; j -- )
printf("%3d", a[j]);
cout << '\n';
}
}
return 0;
}