Recursion vs bitmasking for getting all combinations of vector elements

Question

While practicing for programming competitions (like ACM, Code Jam, etc) I've met some problems that require me to generate all possible combinations of some vector elements.

Let's say that I have the vector {1,2,3}, I'd need to generate the following combinations (order is not important) :

So far I've done it with the following code :

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

Calling getCombinations(0); does the job for me. But is there a better (faster) way? I've recently heard of bitmasking. As I understood it's simply for all numbers between 1 and 2^N-1 I turn that number into a binary where the 1s and 0s would represent whether or not that element is included in the combinations.

How do I implement this efficiently though? If I turn every number into binary the standard way (by dividing with 2 all the time) and then check all the digits, it seems to waste a lot of time. Is there any faster way? Should I keep on using the recursion (unless I run into some big numbers where recursion can't do the job (stack limit))?

"I've met some problems that require me to generate all possible combinations" - I have taken part in my fair share of competitions, and I don't think I've ever seen a problem where doing this would be the correct solution (i.e. efficient enough). You usually need to intelligently generate either a limited subset, just the correct ones, or just count them without generating them. — Bernhard Barker
I mentioned ACM and Code Jam because everyone knows them. Otherwise, I'm a high school student in Macedonia and I take part in national competitions, where the problems are fairly easier than those on the competitions mentioned. I can't think of any, but I am certain that I have used that algorithm to get full points somewhere. — A. Andevski
I have also used variations of that recursion to get subsets of size M, but I am not sure if that can be done with bitmasking efficiently? If it's possible, would like to see that as well. — A. Andevski

nbanic nbanic · Accepted Answer · 2014-05-07T11:43:28

The number of combinations you can get is 2^n, where n is the number of your elements. You can interpret every integer from 0 to 2^n -1 as a mask. In your example (elements 1, 2, 3) you have 3 elements and the masks would therefore be 000, 001, 010, 011, 100, 101, 110, and 111. Let every place in the mask represent one of your elements. For place that has a 1, take the corresponding element, otherwise if the place contains a 0, leave the element out. For example the the number 5 would be the mask 101 and it would generate this combination: 1, 3.

If you want to have a fast and relatively short code for it, you could do it like this:

#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;
}

Recursion vs bitmasking for getting all combinations of vector elements

1 Answers