洛谷：P1157：组合的输出

题目

P1157：组合的输出

分析

这是一个排列组合的题目，而排列组合最好是用位掩码表示。按照题目给出的测试数据，\(\binom{3}{5}\)应该按照升序输入如下10个组合（升序）以及对应的二进制掩码：

我们发现，排列的升序并不严格对应掩码的升序！比如，1 2 5应该先于1 3 4出现，但其对应的掩码却是01101 (1 3 4) < 10011 (1 2 5)！

再仔细观察，我们发现，如果按照降序排列，掩码可以严格保持降序：

但这么一来，实际排列并不是我们需要的排列了（5 4 3 => 3 4 5，而我们需要1 2 3），但这是一个线性转换，容易写出转换的代码：

if (count == r)  // exactly r numbers
{
    for (int i = r - 1; i >= 0; i--)
    {
        cout << setw(3) << n - a[i];
    }
    cout << endl;
}

对于5, 4, 3，其对应的位是[4 3 2 ...]，用n减去这个“位置”就正好是我们需要的1 2 3。

这就是本题的核心解法。

int total = (1 << n);
for (int S = total - 1; S >= 0; S--)
{
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        if (S & (1 << i))  // Masked
        {
            a[count] = i;
            count++;
        }
    }
    if (count == r)  // exactly r numbers
    {
        for (int i = r - 1; i >= 0; i--)
        {
            cout << setw(3) << n - a[i];
        }
        cout << endl;
    }
}

答案

思考

本题虽然说不太难，但是要想清楚几点：

1. S的生成需要降序。
2. 掩码的设定需要由低到高，保证最高位置代表的数字出现在最后
3. 遍历位置需要降序（和S一致），并进行转换。