Given a set of elements now we need to print its powerset

Wikipedia defines powerset as the set of all subsets of S, including the empty set and S itself . Put simply, if the set S is as follows

S = {1,2,3,4}

Then Its powerset P = { {1},{2},{3},{4},{2,3},{2,4},{3,4},{1,3},{1,4},{1,2},{1,3,4},{1,2,3},{1,2,4},{2,3,4},{1,2,3,4},{empty} }

Note that this contains the set itself as well as the empty set. Also note that {1,2} is considered indistinguishable from {2,1}. Two sets are considered identical if they have the same elements even if the order in which those elements appear are different.

The first approach to generate the powerset makes use of the recursive nature of the problem. The powerset of {1,2,3,4} is the union of the power-sets of {1,2,3}, {1,3,4}, {2,3,4}, {1,2,4} and {1,2,3,4} (the set itself).

P(1234) = {1,2,3,4} + P(123) + P(134) + P(234) + P(124), + represents union operation

Therefore we proceed top down and arrive at the following pseuo-code :

powerset(set,string)

1.  add current string to set
2.  for each char in string
3.      substring = string excluding current char
4.      powerset(set,substring)

So now lets begin with the actual development:

package test;

import java.util.HashSet;
import java.util.Set;

public class PowerSet {
    
    public static void powerSet(Set<String> power,String elements, int len){
        if(len > 0){
            power.add(elements);
            for(int i=0;i<elements.length();i++){
                powerSet(power, subSetWithoutIthElement(elements, i), len-1);
            }
        }
    }
    
    private static String subSetWithoutIthElement(String elements,int i){
        StringBuilder sb = new StringBuilder();
        char c[] = elements.toCharArray();
        for(int j=0;j<c.length;j++){
            if(j!=i){
                sb.append(c[j]);
            }
        }
        return sb.toString();
    }
    public static void main(String args[]){
        Set<String> set = new HashSet<String>();
        powerSet(set, "1234", 4);
        System.out.println(set.toString());
    }
}

Note that the empty set is not generated in this approach and we need to add it explicitly.

Another way of approaching the problem is iterative. Note that the total number of elements in the powerset is 2^N where N is the number of elements in the original set S. The total number of binary strings of length N is also 2^N. As it so happens, there is a one-to-one mapping between the two.

Let us consider a binary string of length N. Eg,
 

S = {1,2,3,4}
B = {0,1,1,0}

1 in the binary string represents that the corresponding element from S is included in the set, 0 means its not. Therefore the above binary string represents the set {2,3}. Similarly, it should be possible to generate the powerset by generating all binary strings of length N and adding the sets the represent into the powerset. The pseuo-code is as follows

1. generate a binary string of len N
2. generate the set represented by this string
3. check if this set is already present in the powerSet
4. if not, add it to the powerset
public class PowerSet {
    
    public static Set<String> powerSet = new HashSet<String>();
    
    public static void generatePowerSet(String elements){
        generateBinaryString(elements, elements.length(), "");
    }
    
    public static void generateBinaryString(String elements,int length,String binaryString){
        if(length > 0){
            generateBinaryString(elements,length-1, binaryString + "0");
            generateBinaryString(elements,length-1, binaryString + "1");
        }
        else
            addToPowerSet(elements, generateSet(binaryString, elements));
    }
    
    public static String generateSet(String binaryString,String elements){
        StringBuilder sb = new StringBuilder();
        for(int j=0;j<elements.length();j++)
            if(binaryString.charAt(j) == '1')
                sb.append(elements.charAt(j));
        return sb.toString();
    }
    
    public static void addToPowerSet(String elements, String newSet){
        powerSet.add(newSet);
    }
    
    public static void main(String args[]){
        String elements = "1234";
        generatePowerSet(elements);
        System.out.println(powerSet.toString());
        System.out.println(powerSet.size());
    }
}

The function generateBinaryString() generates all the binary strings of length N recusively by breaking the problem down as follows.

S(all binary strings of len N) = S(all binary strings of len N-1 followed by 0) + S(all binary strings of len N-1 followed by 1).

Shown below is an alternative iterative implementation for generating binary strings. Everything else stays the same.

public class PowerSet {
    
    public static Set<String> powerSet = new HashSet<String>();
    
    public static void generatePowerSet(String elements){
        generateBinaryString(elements, elements.length());
    }
    
    public static void generateBinaryString(String elements,int length){
        StringBuilder sb = null;
        int total = (int) Math.pow(2, length);
        for(int i=0;i<total;i++){
            sb = new StringBuilder();
            for(int j=0;j<=length;j++){
                if((i & (1 << j))!=0){
                    sb.append(elements.charAt(j));
                }
            }
            addToPowerSet(elements, sb.toString());
        }            
    }
    
    public static String generateSet(String binaryString,String elements){
        StringBuilder sb = new StringBuilder();
        for(int j=0;j<elements.length();j++)
            if(binaryString.charAt(j) == '1')
                sb.append(elements.charAt(j));
        return sb.toString();
    }
    
    public static void addToPowerSet(String elements, String newSet){
        powerSet.add(newSet);
    }
    
    public static void main(String args[]){
        String elements = "1234";
        generatePowerSet(elements);
        System.out.println(powerSet.toString());
        System.out.println(powerSet.size());
    }
}

Algorithm 12 Google 12 Amazon 12

FOLLOW US ON LinkedIn



Explore Tutu'rself