Make delicious recipes!

Find powerset of a given set



Problem: Given a set of numbers, find the powerset of that set.
Powerset of a set is defined as the set of all the subsets.
Example: If the given set is [a,b,c], then powerset is [ [1], [2], [3], [1,2], [2,3], [1,3], [1,2,3], [] ]

Solution: Since every possible subset has to be included in the powerset, this implies that the number of sets in the powerset would be 2n where n is the number of elements in the original set.
This 2n comes into play because every element in the set can be included or omitted, giving us 2 possibilities for each element in the set.
So, total number of possibilities = 2x2x2x... = 2n

A recursive solution for this is as follows:

List <List<Integer>> powerSets; // kept global to avoid passing as an argument
void findPowerSet (List<Integer> originalSet, int pos, List<Integer> currSet)
{
    if (originalSet == null)
        return null;
        
    if (pos >= originalSet.size() )
    {
        powerSets.add(currSet);
        return;
    }

    List<Integer> currSet2 = currSet.clone();
    currSet.push (originalSet.get(pos));

    findPowerSet (originalSet, pos+1, currSet);
    findPowerSet (originalSet, pos+1, currSet2);
}


Example execution:
An example running the above algorithm on [1,2,3] is as follows:

pos=0                   [ 1 ]cs1                            [     ]cs2
                       /     \                             /      \
                      /       \                           /        \
                     /         \                         /          \
                    /           \                       /            \
pos=1          [1,2]cs1          [ 1 ]cs2             [ 2 ]cs1        [  ]cs2
              /    \            /    \              /    \          /   \
             /      \          /      \            /      \        /     \
pos=2 [1,2,3]cs1  [1,2]cs2  [1,3]cs1   [1]cs2     [2,3]cs1 [2]cs2  [3]cs1  [ ]cs2


pos=3    (currSet is added to the global powerSet at this stage)



Order analysis: Stack depth goes to 'n' in every recursion leg.
The number of recursion legs is 2n.
This means that in each leg of recursion, the call-stack is pushed and popped n times.
So total push-pop operations is n*2n.

Non-recursive solution: The number of subsets in the powerset is 2n. If we run a loop from 0 to 2n and create a subset having numbers corresponding to 1s in the binary representation of loop variable, then we will create 2n subsets covering the entire range of the powerset.
This can be implemented as:

List <List<Integer>> findPowerSet (List <Integer> originalSet)
{
    int count = originalSet.size();
    long subsetCount = 2 << count;

    List <List<Integer>> powerSet = new ArrayList <List <Integer>>();

    for (long i=0; i < susbsetCount; i++)
    {
        List <Integer> subset = new ArrayList <Integer> ();
        powerSet.add(subset);

        // Add numbers to subset corresponding to 1s in the binary representation of i
        long j=i;
        int pos=0;
        while (j > 0) 
        {
            if (j&1 != 0)
                subset.add (originalSet.get(pos));
            j = j>>1;
            pos++;
        }
    }

    return powerSet;
}




Runtime of the above solution is also exponential but it atleast saves the stack space.
Note: The above function will work only for sets with size less than sizeof(long)=64.

Example execution:
For a set [1,2,3], the execution will be:

subsetCount=8

i=0, subset=[]
i=1, subset=[1]
i=2, subset=[2]
i=3, subset=[1,2]
i=4, subset=[3]
i=5, subset=[1,3]
i=6, subset=[2,3]
i=7, subset=[1,2,3]

powerSet = combination of all the above sets.


Further optimization: Consider the powerset for [a,b]
It would be Pa,b = [ [a], [b], [a,b], [] ]
If we add one more variable to the original set and make it [a,b,c], then the powerset becomes:
Pa,b,c = Pa,b + set formed by adding c to each set in Pa,b

This is a recursive relation like F1(n) = F2(F1(n-1)) i.e a function which can be expressed as some transform of a lower-order function

ArrayList <ArrayList<Integer>> findPowerSet (ArrayList <Integer> originalSet, int pos)
{
    if (originalSet == null)
        return null;

    if (pos == originalSet.size())
    {
        ArrayList<ArrayList<Integer>> powerSet = new ArrayList <ArrayList<Integer>>();
        ArrayList<Integer> subset = new ArrayList<Integer>();
        powerSet.add(subset);
        return powerSet; // return powerset with 1 element as [ [] ]
    }

    ArrayList<ArrayList<Integer>> subPowerSet = findPowerSet(originalSet, pos+1);

    int currentVal = originalSet.get(pos);
    
    
    // copy each subset into a new one, and add current element to it
    ArrayList<ArrayList<Integer>> subPowerSet2 = new ArrayList<ArrayList<Integer>> ();
    
    for (ArrayList <Integer> subset : subPowerSet)
    {
        ArrayList <Integer> subset2 = subset.clone();
        subset2.add(currentVal);
        subPowerSet2.add(subset2);
    }


    // merge the two sub-powersets into one
    subPowerSet.addAll(subPowerSet2);
    return subPowerSet;
}



Example execution:
For a set [1,2,3], the execution will be:
pos=0 --> recurses to --> 1 -- recurses to --> 2 -- recurses to --> 3
pos=3, return [ [] ]
pos=2, subPowerSet     = [ [] ]
       subPowerSet2    = [ [3] ]
       return powerSet = [ [], [3] ]
       
pos=1, subPowerSet     = [ [], [3] ] 
       subPowerSet2    = [ [2], [3,2] ]
       return powerSet = [ [], [3], [2], [3,2] ]
       
pos=0, subPowerSet     = [ [], [3], [2], [3,2] ]
       subPowerSet2    = [ [1], [3,1], [2,1], [3,2,1] ]
       return powerSet = [ [], [3], [2], [3,2], [1], [3,1], [2,1], [3,2,1] ]

Call-stack depth of this function is O(n) and number of recursion legs is 1.
Due to this, improvement over first function is clear enough.
Improvement over second function is that it does not do any bitwise operations to get the elements in each step.
And because of that the limit of 64 elements (sizeof(long)) in the original-set is removed.






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal