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
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 )