javascript-algorithms
Power Set
Power set of a set S is the set of all of the subsets of S, including the
empty set and S itself. Power set of set S is denoted as P(S).
For example for {x, y, z}, the subsets
are:
{
{}, // (also denoted empty set ∅ or the null set)
{x},
{y},
{z},
{x, y},
{x, z},
{y, z},
{x, y, z}
}
Here is how we may illustrate the elements of the power set of the set {x, y, z} ordered with respect to
inclusion:
Number of Subsets
If S is a finite set with |S| = n elements, then the number of subsets
of S is |P(S)| = 2^n. This fact, which is the motivation for the
notation 2^S, may be demonstrated simply as follows:
First, order the elements of
Sin any manner. We write any subset ofSin the format{γ1, γ2, ..., γn}whereγi , 1 ≤ i ≤ n, can take the value of0or1. Ifγi = 1, thei-th element ofSis in the subset; otherwise, thei-th element is not in the subset. Clearly the number of distinct subsets that can be constructed this way is2^nasγi ∈ {0, 1}.
Algorithms
Bitwise Solution
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.
abc |
Subset | |
|---|---|---|
0 |
000 |
{} |
1 |
001 |
{c} |
2 |
010 |
{b} |
3 |
011 |
{c, b} |
4 |
100 |
{a} |
5 |
101 |
{a, c} |
6 |
110 |
{a, b} |
7 |
111 |
{a, b, c} |
See bwPowerSet.js file for bitwise solution.
Backtracking Solution
In backtracking approach we’re constantly trying to add next element of the set to the subset, memorizing it and then removing it and try the same with the next element.
See btPowerSet.js file for backtracking solution.