How to generate a power set of a given set?

Question

I am studying for an interview and I stumbled upon this question online under the "Math" category.

Generate power set of given set:

int A[] = {1,2,3,4,5};   int N = 5;  int Total = 1 << N; for ( int i = 0; i < Total; i++ ) {   for ( int j = 0; j < N; j++) {   if ( (i >> j) & 1 )        cout << A[j];     }   cout <<endl;   } 

Please I do not want an explicit answer. I just want clarifications and hints on how to approach this problem.

I checked power set algorithm on google and I still do not understand how to address this problem.

Also, could someone reiterate what the question is asking for.

Thank you.

Answer 1

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.

Answer 2

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], []]