forked from mberktas/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
bwPowerSet.js
34 lines (29 loc) · 1.28 KB
/
bwPowerSet.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Find power-set of a set using BITWISE approach.
*
* @param {*[]} originalSet
* @return {*[][]}
*/
export default function bwPowerSet(originalSet) {
const subSets = [];
// We will have 2^n possible combinations (where n is a length of original set).
// It is because for every element of original set we will decide whether to include
// it or not (2 options for each set element).
const numberOfCombinations = 2 ** originalSet.length;
// Each number in binary representation in a range from 0 to 2^n does exactly what we need:
// it shows by its bits (0 or 1) whether to include related element from the set or not.
// For example, for the set {1, 2, 3} the binary number of 0b010 would mean that we need to
// include only "2" to the current set.
for (let combinationIndex = 0; combinationIndex < numberOfCombinations; combinationIndex += 1) {
const subSet = [];
for (let setElementIndex = 0; setElementIndex < originalSet.length; setElementIndex += 1) {
// Decide whether we need to include current element into the subset or not.
if (combinationIndex & (1 << setElementIndex)) {
subSet.push(originalSet[setElementIndex]);
}
}
// Add current subset to the list of all subsets.
subSets.push(subSet);
}
return subSets;
}