Generating combinations or subsets using bitwise operations

Generating combinations or subsets using bitmasks.

Combinations_Bitwise The idea behind this algorithm is to mask the positions in an array using bitmask and select only the unmasked numbers. Each mask generates a unique combination.
The number of mask(s) is equal to 2n - 1, where ‘n’ is the number of elements in the array.

Example:
Consider the mask [ 0 1 1 ], when this mask is applied on array of numbers [ 1, 2, 3 ],
only the positions 0 is masked and numbers at positions 1 and 2 are selected and we get a
combination ( 2, 3 ).

Similary consider the mask [ 1 0 1 ], when this mask is applied on the same array,
only the position 1 gets masked and numbers at positions 0 and 3 are selected
i.e numbers 1 and 3 and we get the combination ( 1, 3 ).

Thus for an array of size 3 we have 23 - 1 masks each of which generates a unique combination.




Python

Python Program for generating combinations or subsets using bitwise operations


C++14 Program for 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 )

Copyright (c) 2019-2021, Algotree.org.
All rights reserved.