Generating combinations (subsets) using bitwise operations
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 2n, ‘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 23 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 )
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
class Combinations {
void GetCombinationsBitwise (List<Integer> nums) {
int sz = nums.size();
List<List<Integer>> combinations = new ArrayList<>(); // For storing all possible combinations
for (int mask = 0; mask < (1<<sz); mask++) {
List<Integer> comb = new ArrayList<>(); // 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)) != 0) {
comb.add(nums.get(pos));
}
}
combinations.add(comb);
}
for (int i = 0; i < combinations.size(); i++) {
System.out.print ("( ");
for (int j = 0; j < combinations.get(i).size(); j++) {
System.out.print (combinations.get(i).get(j) + " ");
}
System.out.println (")") ;
}
}
public static void main (String[] arr) {
Combinations c = new Combinations();
List<Integer> nums = Arrays.asList(42, 20, 33, 8);
c.GetCombinationsBitwise(nums);
}
}
Output
( )
( 42 )
( 20 )
( 42 20 )
( 33 )
( 42 33 )
( 20 33 )
( 42 20 33 )
( 8 )
( 42 8 )
( 20 8 )
( 42 20 8 )
( 33 8 )
( 42 33 8 )
( 20 33 8 )
( 42 20 33 8 )