How to generate a power set of a given set?

Power set of a set A is the set of all of the subsets of A.

Not the most friendly definition in the world, but an example will help :

Eg. for {1, 2}, the subsets are : {}, {1}, {2}, {1, 2}

Thus, the power set is {{}, {1}, {2}, {1, 2}}

---

To generate the power set, observe how you create a subset : you go to each element one by one, and then either retain it or ignore it.

Let this decision be indicated by a bit (1/0).

Thus, to generate {1}, you will pick 1 and drop 2 (10).

On similar lines, you can write a bit vector for all the subsets :

• {} -> 00
  {1} -> 10
  {2} -> 01
  {1,2} -> 11

To reiterate : A subset if formed by including some or all of the elements of the original set. Thus, to create a subset, you go to each element, and then decide whether to keep it or drop it. This means that for each element, you have 2 decisions. Thus, for a set, you can end up with 2^N different decisions, corresponding to 2^N different subsets.

See if you can pick it up from here.

Power set is just set of all subsets for given set. It includes all subsets (with empty set). It's well-known that there are 2^N elements in this set, where N is count of elements in original set.

To build power set, following thing can be used:

• Create a loop, which iterates all integers from 0 till 2^N-1
• Proceed to binary representation for each integer
• Each binary representation is a set of N bits (for lesser numbers, add leading zeros). Each bit corresponds, if the certain set member is included in current subset.

Example, 3 numbers: a, b, c

number binary  subset
0      000      {}
1      001      {c}
2      010      {b}
3      011      {b,c}
4      100      {a}
5      101      {a,c}
6      110      {a,b}
7      111      {a,b,c}

Create a power-set of: {"A", "B", "C"}.

---

Pseudo-code:

val set = {"A", "B", "C"}

val sets = {}

for item in set:
  for set in sets:
    sets.add(set + item)
  sets.add({item})
sets.add({})

---

Algorithm explanation:

1) Initialise sets to an empty set: {}.

2) Iterate over each item in {"A", "B", "C"}

3) Iterate over each set in your sets.

3.1) Create a new set which is a copy of set.

3.2) Append the item to the new set.

3.3) Append the new set to sets.

4) Add the item to your sets.

4) Iteration is complete. Add the empty set to your resultSets.

---

Walkthrough:

Let's look at the contents of sets after each iteration:

Iteration 1, item = "A":

sets = {{"A"}}

Iteration 2, item = "B":

sets = {{"A"}, {"A", "B"}, {"B"}}

Iteration 3, item = "C":

sets = {{"A"}, {"A", "B"}, {"B"}, {"A", "C"}, {"A", "B", "C"}, {"B", "C"}, {"C"}}

Iteration complete, add empty set:

sets = {{"A"}, {"A", "B"}, {"B"}, {"A", "C"}, {"A", "B", "C"}, {"B", "C"}, {"C"}, {}}

The size of the sets is 2^|set| = 2^3 = 8 which is correct.

---

Example implementation in Java:

public static <T> List<List<T>> powerSet(List<T> input) {
  List<List<T>> sets = new ArrayList<>();
  for (T element : input) {
    for (ListIterator<List<T>> setsIterator = sets.listIterator(); setsIterator.hasNext(); ) {
      List<T> newSet = new ArrayList<>(setsIterator.next());
      newSet.add(element);
      setsIterator.add(newSet);
    }
    sets.add(new ArrayList<>(Arrays.asList(element)));
  }
  sets.add(new ArrayList<>());
  return sets;
}

Input: [A, B, C]

Output: [[A], [A, C], [A, B], [A, B, C], [B], [B, C], [C], []]