Algotree > Algorithms > Numeric > Generating combinations or subsets using bitwise operations

Generating combinations or subsets using bitwise operations

Generating combinations or subsets using bitmasks.

The idea of this algorithm is to mask positions in an array using bitmask and collect only the unmasked combination(s).
The number of mask(s) is equal to 2^n - 1, where ‘n’ is the number of elements in the array.

Combinations using bitmask

C++14 Generating combinations or subsets using bitwise operations

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
typedef vector<vector<int>> VVI;

VVI GetCombinationsBitwise(vector<int>& vec){

     int sz = vec.size();
     vector<vector<int>> combinations;

     for(int mask=0; mask < (1<<sz); mask++){
         vector<int> comb;
         for(int pos=0; pos<sz; pos++){
             if(mask & (1 << pos)) {
                 comb.push_back(vec[pos]);
             }   
         }   
         combinations.push_back(comb);
     }   

     for(int i=0; i < combinations.size(); i++){
         cout << "( ";
         for(int j=0; j < combinations[i].size(); j++){
             cout << combinations[i][j] << " ";
         }   
         cout << ")" << endl;
     }   

     return combinations;
}

int main(){

    // This type of vector initialization needs support for c++11 in the compiler
    vector<int> vec = { 1, 2, 3, 4}; 
    vector<vector<int>> combinations = GetCombinationsBitwise(vec);
    return 0;
}

Output

( )
( 1 )
( 2 )
( 1 2 )
( 3 )
( 1 3 )
( 2 3 )
( 1 2 3 )
( 4 )
( 1 4 )
( 2 4 )
( 1 2 4 )
( 3 4 )
( 1 3 4 )
( 2 3 4 )
( 1 2 3 4 )