10
\$\begingroup\$

I am trying to get a powerset (all subsets of a set) in Java. So my logic for that is:

  1. A given set is one subset, so add so it as it is to result.
  2. Remove each element of set from given set and we will get all the combinations for 1 element less. Add these results to final result.
  3. Recursively find subsets of all sets from step 2 and add to result.

I tried searching for a similar solution on Stack Overflow but did not get one. Is this a clean way to implement it?

import java.util.*;

public class PowerSet {
    public static <E> Set<Set<E>> findPowerSet(Set<E> set){
        Set<Set<E>> ret = new HashSet<Set<E>>();
        ret.add(set);
        if(set.isEmpty()){
            return ret;
        }
        Iterator<E> it = set.iterator();
        while(it.hasNext()){
            Set<E> tmp = new HashSet<E>(set);   //create a copy of current set
            tmp.remove(it.next());              //remove current element from copy set
            ret.add(tmp);                       //add the remaining set to result
            ret.addAll(findPowerSet(tmp));      //recursively find subsets of copy set
        }
        return ret;
    }

    public static void main(String[] args) {
        Set<Character> set = new HashSet<Character>();
        set.add('a');set.add('b');set.add('c');
        System.out.println("Input set");        printSet(set);
        System.out.println("\nsub sets");
        findPowerSet(set).stream().forEach(PowerSet::printSet);
    }

    public static <E> void printSet(Set<E> set){
        StringBuilder sb = new StringBuilder(set.size()==0 ? "{}\n" :"{");
        Iterator<E> it = set.iterator();
        while(it.hasNext()){
            sb.append(it.next().toString())
            .append(it.hasNext()? ", " : "}\n");
        }
        System.out.print(sb.toString());
    }
}
\$\endgroup\$
  • \$\begingroup\$ Seems like it should work. Another way to do this is start with an empty set and build up. For example, a set of N elements corresponds to a binary number with N bits. Starting at zero, count up. Each bit set is an element in a new set. Stop when all bits are one. \$\endgroup\$ – markspace Jun 1 '17 at 1:57
3
\$\begingroup\$

I tried to do the same thing, basically using binary numbers & counting the bits instead. Let some number binarySet have the same number of bits as the input set has elements. Then just count up from zero. For each bit in the binary number, that bit corresponds to an element in the input set. If the bit is set (1, not 0) then add the corresponding element to a set to be included in the power set.

After implementing it this way, my only criticism of your approach is that your approach seems more complicated than necessary. The binary number approach is compact and fairly easy to follow.

P.S. I checked here https://softwareengineering.stackexchange.com/questions/272061/why-doesnt-java-have-optimization-for-tail-recursion-at-all and it appears that Java does not offer optimization for tail recursion. That would be another criticism for any method in Java using tail recursion, I'd recommend that it manually change to using a loop.

public class PowerSet {

    static <T> Set<Set<T>> powerSet( Set<T> set ) {
        T[] element = (T[]) set.toArray();
        final int SET_LENGTH = 1 << element.length;
        Set<Set<T>> powerSet = new HashSet<>();
        for( int binarySet = 0; binarySet < SET_LENGTH; binarySet++ ) {
            Set<T> subset = new HashSet<>();
            for( int bit = 0; bit < element.length; bit++ ) {
                int mask = 1 << bit;
                if( (binarySet & mask) != 0 ) {
                    subset.add( element[bit] );
                }
            }
            powerSet.add( subset );
        }
        return powerSet;
    }

    public static void main(String[] args) {
        Set<Character> test = new HashSet<>();
        test.add( 'a' );
        test.add( 'b' );
        test.add( 'c' );
        System.out.println("test = " + test);
        Set<Set<Character>> result = powerSet( test );
        System.out.println( result );
    }
}

Output:

run:
test = [a, b, c]
[[], [a], [b], [a, b], [c], [a, c], [b, c], [a, b, c]]
BUILD SUCCESSFUL (total time: 0 seconds)
\$\endgroup\$
  • \$\begingroup\$ +1, but the tail recursion argument is not very relevant, because in practice you will reach the limit of memory much sooner than the limit of the call stack \$\endgroup\$ – janos Jun 1 '17 at 5:50
  • \$\begingroup\$ This seems to be less of a review and more of a "here's how I did it", which isn't an answer here. Could you edit your answer to contain an actual review? \$\endgroup\$ – Nic Hartley Jun 1 '17 at 16:50
4
\$\begingroup\$
        if(set.isEmpty()){
            return ret;
        }

This is unnecessary. If the set is empty, the iterator will return false to the first hasNext(), and you'll go straight to the final return ret;.

Other than that, it seems like a simple, obviously correct, approach.

However, it is quite inefficient.

        Iterator<E> it = set.iterator();
        while(it.hasNext()){
            Set<E> tmp = new HashSet<E>(set);   //create a copy of current set
            tmp.remove(it.next());              //remove current element from copy set
            ret.add(tmp);                       //add the remaining set to result
            ret.addAll(findPowerSet(tmp));      //recursively find subsets of copy set
        }
        return ret;
    }

Suppose that we call it with a set of \$n\$ elements. The outermost call produces a set of \$2^n\$ subsets by taking the union of \$n\$ subresults, each of \$2^{n-1}\$ elements. So the outermost call discards as duplicates \$(n-2)2^{n-1}\$ subsets. But, of course, each of those recursive calls discarded \$(n-3)2^{n-2}\$ subsets from their subresults, etc.

This is why the typical simple implementation is to build up from the empty set.

An advanced implementation, which isn't always better but can reduce copying in some use cases, is to write a custom iterator which uses a Gray code to add or remove precisely one element in each call to next().

\$\endgroup\$
1
\$\begingroup\$

Like Peter already answered, you are adding the same subsets a lot (which are automatically removed since a Set cannot contain duplicates).

markspace solves this problem by using bit manipulations which is awesome, but might not be what you prefer. So I'll propose a different approach that uses the same general idea that you use, but optimised to not add doubles.

The main idea goes like this:

  • Take 1 element out of the set
  • find the powerset of the remaining elements.
  • add all those subsets to the result
  • add the element we removed to each of those subsets and add these new sets to the result as well

In code that would look like this:

public static <E> Set<Set<E>> findPowerSet(Set<E> set) {
    Set<E> result = new HashSet<>(set);
    return findPowerSetDestructive(result);
}

private static <E> Set<Set<E>> findPowerSetDestructive(Set<E> set){
    Set<Set<E>> ret = new HashSet<>();
    if(set.isEmpty()){
        ret.add(new HashSet<E>());
        return ret;
    }
    E current = set.iterator().next();
    set.remove(current);
    Set<Set<E>> subsets = findPowerSetDestructive(set);
    ret.addAll(subsets);
    for (Set<E> subset : subsets) {
        Set<E> newSubSet = new HashSet<E>(subset);
        newSubSet.add(current);
        ret.add(newSubSet);
    }
    return ret;
}

I added a helper method that literally takes out an element from the input set. That's why the original method copies the input set and starts off the destructive method with this safe copy. This way, we don't need to worry about the original input set being modified.


But can we do better? Like @markspace mentioned java doesn't really like recursive calls that much. Instead we can also build the result set from the ground up. The algorithm then becomes

  • loop over all elements of the input set
  • copy the power set we got from the previous elements
  • add the current element to each of the sets in that power set
  • add all those new sets to the result

Again, turning this into java code could look like this:

public static <E> Set<Set<E>> findPowerSet2(Set<E> set){
    Set<Set<E>> result = new HashSet<>();
    result.add(new HashSet<E>());
    for(E element : set){
        Set<Set<E>> previousSets = new HashSet<>(result);
        for (Set<E> subSet : previousSets) {
            Set<E> newSubSet = new HashSet<E>(subSet);
            newSubSet.add(element);
            result.add(newSubSet);
        }
    }
    return result;
}
\$\endgroup\$
-1
\$\begingroup\$

It's good - but it's not object-oriented! All your methods are static and I guess that's fine but it's a procedural way of thinking. We can't instantiate a PowerSet (in fact, we can but it's useless). In your example, once you recieve your set of sets, the entire semantic that it's a powerset has been lost.

What would be better is if a PowerSet object was useful for something. Perhaps we could implement Set or Collection. I suggest we implement Iterable. Because it's easy and I'm lazy.

public class PowerSet<E> implements Iterable<Set<E>>
{
    private final Set<Set<E>> sets;

    public PowerSet(final Set<E> input)
    {
        sets = findPowerSet(input);
    }

    private static Set<Set<E>> findPowerSet(final Set<E> set)
    {
        // Identical to your code, but now private! (also made the param final)
    }

    public void print()
    {
        // Now non-static! Implement it yourself :)
    }

    public Iterator<Set<E>> iterator()
    {
        return sets.iterator(); // Just delegate to our set of sets
    }
}

Our PowerSet object is now useful! We can use it like this:

PowerSet<Character> pset = new PowerSet<>(set);
pset.print();

or

for(Set<Character> foo : pset)
{
    foo.toArray();
}

I would also go one step further and use Collections.unmodifiableSet to enforce that a user cannot modify the powerset, thereby invalidating it.

You could provide a method to return the original set, if you wanted.

\$\endgroup\$
  • \$\begingroup\$ I fully disagree with the"it's a procedural way of thinking". This is a functional way of thinking. You have an object (a set of something) and the function that transforms this set into the set of all it's subsets (aka the powerset). No semantics are lost if you write Set<Set<Character>> powerset = Powerset.findPowerSet(mySet) either. \$\endgroup\$ – Imus Jun 2 '17 at 8:58
  • \$\begingroup\$ @Imus The creation of the powerset is somewhat functional. It should produce the same output for every input. Subsequent usage of the powerset is procedural because it relies on things happening in a specific order e.g. PSet set = createSet(); printSet(set); No semantics are lost if you're within the same code block, but once you pass that Set<Set<Character>> down a call hierarchy, however... Thanks for the downvote :) \$\endgroup\$ – Michael Jun 2 '17 at 14:42
  • \$\begingroup\$ If you pass it to something else, then that something else either wants a powerset (and thus uses variable names/comment clarification requesting this), or it doesn't care if it's a powerset at all. Why would you want to enforce this? (Note there are some situations where I too prefer an actual object to work with over a utility class, but this is not one of those situations). \$\endgroup\$ – Imus Jun 2 '17 at 15:13
  • \$\begingroup\$ @Imus "Why would you want to enforce this?" Because it's less error-prone and easier to maintain. I can unit test a PowerSet and have confidence that every time I see an object of that class I know it will work exactly as I expect. You can unit test a static method and know that works, but the resulting Set<Set<X>> is just naked data. Anyone can manipulate it, ruining its representation of a powerset. If you're passing Set<Set<X>> down a call hierarchy, any one of those methods is a potential source of problems. That's not the case in my implementation. \$\endgroup\$ – Michael Jun 2 '17 at 16:03
  • \$\begingroup\$ This is good suggestion. I made it static for simplicity. \$\endgroup\$ – Satyen Shimpi Jun 7 '17 at 2:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.