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

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 2ⁿ - 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 2³ - 1 masks each of which generates a unique combination.

Python

Python Program for generating combinations or subsets using bitwise operations

def GetCombinationsBitwise(array):

     sz = len(array)
     all_combinations = []

     # 1<<sz is the left shift operator which is equal to 1*2^(sz)
     for mask in range ((1<<sz)):
         comb = []
         for pos in range(sz):
             if (mask & (1 << pos)):
                 comb.append(array[pos])
         all_combinations.append(comb);

     for comb in (all_combinations):
         print(comb)

def main():

    array = [ 1, 2, 3, 4 ] 
    GetCombinationsBitwise(array)

if __name__ == "__main__":
    main()

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]

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 )