用于获取向量元素的所有组合的递归与位掩码

Question

在为编程竞赛（如 ACM、Code Jam 等）练习时，我遇到了一些问题，需要我生成一些向量元素的所有可能组合。

假设我有向量 {1,2,3}，我需要生成以下组合（顺序不重要）：

1
2
3
1 2
1 3
2 3
1 2 3

到目前为止，我已经使用以下代码完成了它：

void getCombinations(int a)
{
    printCombination();
    for(int j=a;j<vec.size();j++)
    {
        combination.pb(vec.at(j));
        getCombinations(j+1);
        combination.pop_back();
    }
}

调用 getCombinations(0); 为我做这项工作。但是有更好（更快）的方法吗？我最近听说了位掩码。据我所知，它只是针对 1 到 2^N-1 之间的所有数字，我将该数字转换为二进制，其中 1 和 0 表示该元素是否包含在组合中。

我如何有效地实现这一点？如果我把每个数字都按照标准的方式（一直除以 2）变成二进制，然后检查所有的数字，似乎浪费了很多时间。有没有更快的方法？我是否应该继续使用递归（除非我遇到一些递归无法完成工作的大数字（堆栈限制））？

Answer 1

您可以获得的组合数为 2^n，其中 n 是您的元素数。您可以将 0 到 2^n -1 之间的每个整数解释为掩码。在您的示例（元素 1、2、3）中，您有 3 个元素，因此掩码为 000、001、010、011、100、101、110 和 111。让掩码中的每个位置代表您的元素之一。对于有 1 的地方，取相应的元素，否则如果该地方包含 0，则将该元素排除在外。例如，数字 5 将是掩码 101，它将生成以下组合：1、3。

如果你想要一个快速且相对较短的代码，你可以这样做：

#include <cstdio>
#include <vector>

using namespace std;

int main(){

    vector<int> elements;

    elements.push_back(1);
    elements.push_back(2);
    elements.push_back(3);

    //  1<<n is essentially pow(2, n), but much faster and only for integers
    //  the iterator i will be our mask i.e. its binary form will tell us which elements to use and which not
    for (int i=0;i<(1<<elements.size());++i){
        printf("Combination #%d:", i+1);
        for (int j=0;j<elements.size();++j){
            //  1<<j shifts the 1 for j places and then we check j-th binary digit of i
            if (i&(1<<j)){
                printf(" %d", elements[j]);
            }
        }
        printf("\n");
    }

    return 0;
}