Algotree > Algorithms > Numeric > Generating combinations (subsets) using bitwise operations

Generating combinations (subsets) using bitwise operations

Combinations_Bitwise The idea behind this algorithm is to mask the positions in an array using bitmask and select only the unmasked numbers. You will notice that each mask (bit combination) is unique, and the number of mask(s) is equal to 2ⁿ, ‘n’ being the number of elements in the array.
If n is 3, then

First mask would be 0 [ 0 0 0 ]
Last mask would be 7 [ 1 1 1 ]

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

Bit shifting

For finding a combination, we check if the bit is set at a position in the mask. If it is set, we include the number from the set.
Example:

Mask	Position	Check if set	Array Elements	Include
1 0 1 1	Position 0 0 0 0 1	1 0 1 1 AND 0 0 0 1 ———— 0 0 0 1 Bit at position 0 is set in the mask	1 2 3 4	1 (Element at 0’th position)
1 0 1 1	Position 1 0 0 1 0	1 0 1 1 AND 0 0 1 0 ———— 0 0 1 0 Bit at position 1 is set in the mask	1 2 3 4	2 (Element at 1’th position)
1 0 1 1	Position 2 0 1 0 0	1 0 1 1 AND 0 1 0 0 ———— 0 0 0 0 Bit at position 2 is NOT set in the mask	1 2 3 4	None
1 0 1 1	Position 3 1 0 0 0	1 0 1 1 AND 1 0 0 0 ———— 1 0 0 0 Bit at position 1 is set in the mask	1 2 3 4	4 (Element at 3’th position)

Thus for a mask [ 1 0 1 1 ] for an array with elements [ 1 2 3 4 ] we get a unique combination [ 1 2 4 ]

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 = []

         #  Check if the bit is set at each position in the mask.
         #  i.e If the mask is [ 1 0 1 1 ], we check for set bit at the below positions
         #  Pos  : 3 2 1 0
         #  Mask : 1 0 1 1
         #  --------------
         #         Y N Y Y

         # Bit shifting is done as below
         # 1 0 1 1                1 0 1 1                1 0 1 1                 1 0 1 1
         #    &                      &                      &                       &
         # 0 0 0 1 (left shift)   0 0 1 0 (left shift)   0 1 0 0  (left shift)   1 0 0 0
         # --------               -------                -------                 --------
         # 0 0 0 1 (0'th set)     0 0 1 0 (1'st set)     0 0 0 0 (2'nd NOT set)  1 0 0 0 (3'rd set)

         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]

#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; // Stores a combination

         /* Check if the bit is set at each position in the mask.
            i.e If the mask is [ 1 0 1 1 ], we check for set bit at the below positions
            Pos  : 3 2 1 0
            Mask : 1 0 1 1
            --------------
                   Y N Y Y

           Bit shifting is done as below
           1 0 1 1                1 0 1 1                 1 0 1 1                 1 0 1 1
               &                     &                       &                      &
           0 0 0 1 (left shift)   0 0 1 0 (left shift)    0 1 0 0  (left shift)   1 0 0 0
           --------               -------                 -------                 --------
           0 0 0 1 (0'th set )    0 0 1 0 (1'st set)      0 0 0 0 (2'nd NOT set)  1 0 0 0 (3'rd set) */

         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 )