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.

Estonian

Power set of a set={a,b} is the set consisting of all possible combination of representing elements of the set taken any or none at a time. Here,P(s)={{a},{b},{ab},{}}; – Ultramicrochemistry

Very interested in recursive algorithm for this problem! – Airlike

Check this answer: https://mcmap.net/q/538151/-creating-a-power-set-of-a-sequence – Whitaker

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.

Facilitation

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

Secessionist

If you added {} at the beginning (rather than the end) then you wouldn't have to explicitly insert the singleton sets at each pass through the outer loop. – Feudality

@JohnColeman Hi John, if we added an empty set at the beginning, then we would iterate over the sets one too many times. After the first iteration we would have {{"A"},{"A"}} which is incorrect. Inserting the empty set is also done outside any loops. Do you mind sharing some code to explain? – Secessionist

But if you have {} at the beginning, wouldn't you have {"A"}, {} after one pass? You are taking the existing sets and creating a copy of each set in it, to which you add the new item. Since you would be adding "A" to the copy -- I don't see how "A" sneaks into the empty set. After all, when you do this with "B" in your loop you get {"A","B"} while still having {"A"} -- that {"A"} isn't replaced by {"A","B"}. You should insert the empty set outside of any loop -- but before the loops, in which case adding the singletons inside the loop is superfluous. – Feudality

@JohnColeman If I start with an empty set {{}}, then as I iterate over the sets I will take the empty set and append 'A' to it. I will then add a new set containing 'A' to the existing sets. Running the code with your suggestion I get the following after the first iteration: [[], [A], [A]] as expected. Running the new algorithm on {'A', 'B', 'C'} I get [[], [C], [B], [B, C], [A], [A, C], [A, B], [A, B, C], [A], [A, C], [A, B], [A, B, C], [B], [B, C], [C]] – Secessionist

You say "I will then add a new set containing 'A' to the existing sets" -- but why would you still do that? The point of my comment is that explicitly adding the item as a singleton (step 4 in your pseudocode) isn't needed if you initialize with the empty set – Feudality

@Secessionist Why are you using a List and not a Set? isn't it better to use a Set in order to ensure that there are no duplicates? – Hurling

@SarahM I use a List to demonstrate that this algorithm doesn't produce duplicates – Secessionist

Very great algo, but it will not work for input containing duplicate element and subset shouldn't have duplicate? – Rembrandt

What is the time complexity of this algorithm? – Rhodonite

Answer 3

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}

Cragsman

why are we converting into binary? I am not getting that. – Dissolution

@PoojaKhatri each bit in the binary number indicates whether an element is present in the current subset or not. Check out the top rated answer for a better explanation. – Beal

Answer 4

Well, you need to generate all subsets. For a set of size n, there are 2ⁿ subsets.

One way would be to iterate over the numbers from 0 to 2ⁿ - 1 and convert each to a list of binary digits, where 0 means exclude that element and 1 means include it.

Another way would be with recursion, divide and conquer.

Tragedienne

I know this thread is old, but I'm very interested in more about the recursive technique. This was an old college Lisp assignment that I never figured out. And I'm still puzzled. – Airlike

@ScottBiggs So am I.. This thing is just confusing! – Juliannejuliano

You can see some recursive examples here: stackoverflow.com/questions/26332412 – Tragedienne

Answer 5

Let's generate the power set of a three-item set. The possible subset will be:

000   
100   
010   
001
110
101
011
111   
   

where 0 indicates no item and 1 indicates an item. The number of possible subsets is 2^(number of items in the set).

Using Python, we can implement this idea as follows:

    def powerSet(items):
        
        N = len(items)
    
        for i in range(2**N):
        
            comb=[]
            for j in range(N):
                if (i >> j) % 2 == 1:
                    comb.append(items[j])
            yield comb
        
    for x in powerSet([1,2,3]):
        print (x)

Microwatt

Answer 6

You Get Something Like This by Implementing the top rated Answer.

def printPowerSet(set,set_size):

    # set_size of power set of a set
    # with set_size n is (2**n -1)
    pow_set_size = (int) (math.pow(2, set_size));
    counter = 0;
    j = 0;

    # Run from counter 000..0 to 111..1
    for counter in range(0, pow_set_size):
        for j in range(0, set_size):

            # Check if jth bit in the 
            # counter is set If set then 
            # pront jth element from set 
            if((counter & (1 << j)) > 0):
                print(set[j], end = "");
        print("");

Mcneal

Answer 7

C# Solution

Time Complexity and Space Complexity: O(n*2^n)

 public class Powerset
    {


        /*
         P[1,2,3] = [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
             */
        public  List<List<int>> PowersetSoln(List<int> array)
        {

            /*
                We will start with an empty subset
                loop through the number in the array
                         loop through subset generated till and add the number to each subsets

              */

            var subsets = new List<List<int>>();
            subsets.Add(new List<int>());

            for (int i = 0; i < array.Count; i++)
            {
                int subsetLen = subsets.Count; 
                for (int innerSubset = 0; innerSubset < subsetLen; innerSubset++)
                {
                    var newSubset = new List<int>(subsets[innerSubset]);
                    newSubset.Add(array[i]);
                    subsets.Add(newSubset);
                }

            }

            return subsets;
        }
    }

Vanadinite

Answer 8

Sample Java Code:

void printPowerSetHelper(String s, String r) {
    if (s.length() > 0) {
        printPowerSetHelper(s.substring(1), r + s.charAt(0));
        printPowerSetHelper(s.substring(1), r);
    } 
    if (r.length() > 0) System.out.println(r);
}

void printPowerSet(String s) {
    printPowerSetHelper(s,"");
}

Kilometer