Generate power set of a set

Given a set S, the Power Set (or powerset) denoted as P(S), is set of all subsets of S. [A set is a collection of certain values, without any particular order, and no repeated values] (link)

If S = {a,b,c}
Power Set, P(S) = { {}, {a}, {b},  {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}

Power Set is the different ways of selecting items from the given set (including none and all elements).  Also, just like a set, the order doesn't matter in power set. If the number of elements in set in 3 then the number of elements in the power set will be 8 i.e. 2^3.

|S| = n
|P(S)| = 2^n 

Algorithm

One of the simplest algorithms for generating all subsets is Binary Counting (Algorithm Design Manual). This approach uses binary representation to get all subsets. To generate all subsets, we need to count from 0 to 2^n - 1. For each integer, successively mask off each of the bits and compose a subset of exactly the items corresponding to 1 bits. 

Any subset of a set can either contain or not contain an element. So there are two states for each element of the set; either it is present or absent. This can be used to derive the formula of 2^n (i.e. 2.2.2.....n times). Two states for each element of the set can be visualized as true/false or (1/0). If a position is true, the element gets added to the result otherwise ignore it. 

let S = {a,b,c}

counter   subsets

000         {}             //all bits are off; so no element is in subset

001         {a}           // LSB or bit at lowest position is 1, so this means the first element is in subset

010         {b}

011         {a,b}

100         {c}

101         {a,c}

110         {b,c}

111         {a,b,c}     //all bits 1, so all elements make to subset

So from the above table, the list of all subsets will give power set. This approach can be used to generate all subsets of a set programmatically.

Java Implementation

Set can contain any type of element, so to generalize we can select generic numbers which denote the index of the element (but be careful that set doesn't support index-related operations).

S = {apple, orange, mango} 

is equivalent to S ={1,2,3}

so first index = apple

2nd index = orange, and so on.

package hacker;

import java.util.ArrayList;
import java.util.List;

/**
 * Generate power sets of a set. if S = {1,2,3} P(S) =
 * {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} generate method just takes a
 * number like 3 for above case.
 */
public class PowerSet {
 private List<List<Integer>> generate(int num) {
  int size = 1 << num;
  System.out
    .format("Set size is %d, and power set size is %d", num, size);

  List<Integer> result;
  List<List<Integer>> output = new ArrayList<>(size);

  for (int i = 0; i < size; i++) {
   result = new ArrayList<>();
   int t = i;
   int count = 1;

   // values to be added in subset
   while (t > 0) {
    // if LSB is one, add corresponding element
    if ((t & 1) > 0) {
     result.add(count);
    }
    count++;
    // shift right by 1 position; so 100 will become 10
    t = t >> 1;
   }
   output.add(result);
  }
  return output;
 }

 public static void main(String[] args) {
  PowerSet ps = new PowerSet();
  int num = 3; // set has 3 elements
  List<List<Integer>> powerset = ps.generate(num);

  System.out.println("\noutput :" + powerset);
 }
}

Output

Set size is 3, and power set size is 8
output :[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

 

Important Points

1. Above approach doesn't generate the subset in lexicographic order. It is bit tricky to generate subsets in lexicographic (sorted) order.
2. Above approach can be used to randomly generate a subset.
3. To generate the next or previous subset using the above approach, just increment or decrement the number by one and then convert that into a subset.
4. Above approach can also be used to used to generate subsets of a fixed length or k-elements (k<n).

References
http://www.mathsisfun.com/sets/power-set.html  

---

keep coding !!!