Algorithm to find powerset of {1,2,3}

Question

I think i'm finding this a little confusing because i've never really used Java sets. Could someone please try and show me (preferably by explaining how the powerset is gradually being created) in the following code (ps i got this code from a post on stackoverflow, so credit goes to that person):

public static void main(String[] args) {
        Set<Integer> mySet = new HashSet<Integer>();
        mySet.add(1);
        mySet.add(2);
        mySet.add(3);
        for (Set<Integer> s : powerSet(mySet)) {
            System.out.println(s);
        }

    }

    public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
        Set<Set<T>> sets = new HashSet<Set<T>>();

        //If the input is empty, add the empty set and return
        if (originalSet.isEmpty()) {
            sets.add(new HashSet<T>());
            return sets;
        }

        //Put the originalSet into an arraylist
        List<T> list = new ArrayList<T>(originalSet);

        //Get the first element
        T head = list.get(0);

        //Get everything but the first element and put into a set
        Set<T> rest = new HashSet<T>(list.subList(1, list.size()));

        //For each element in the set above
        for (Set<T> set : powerSet(rest)) {

            //Create a new set
            Set<T> newSet = new HashSet<T>();

            //Add the head
            newSet.add(head);

            //Add the rest
            newSet.addAll(set);

            //Add all of newset to the result
            sets.add(newSet);

            //Add the current element
            sets.add(set);
        }
        return sets;
    }

Credit does not go to anyone unless you tell us who it is it goes to. That's what credit _means_: that we, the readers, _get to know_ who did the work. — hmakholm left over Monica, Aug 30 '11 at 17:16
As for the question: how comfortable are you with recursion? In other words, is the question about understanding the recursive algorithm or about being able to read the particular details of the Java implementation? — hmakholm left over Monica, Aug 30 '11 at 17:19
Were you referring to this one? http://stackoverflow.com/questions/1670862/obtaining-powerset-of-a-set-in-java . If yes, please include that link in your question. — Kal, Aug 30 '11 at 17:19
http://stackoverflow.com/questions/1422626/algorithm-for-calculating-the-power-set — Tae-Sung Shin, Aug 30 '11 at 17:20
It looks pretty well commented to me. What part(s) is/are confusing? — Bart Kiers, Aug 30 '11 at 17:56
I did the commenting, i just cant see how this results in the powerset. If our original set was {1,2,3} when we are 'on' 1, how do we skip '2' to grab '3' and create the set {1,3} for example? — James T, Aug 30 '11 at 19:14
The comment `for each element in the set above` should be `for each subset of the rest set`. If 1 is the first element, then the recursive call generates the power set of {2,3}, that is, the sets {2,3}, {2}, {3}, {}. The loop then takes each of these emits it either with or without the 1. — hmakholm left over Monica, Aug 30 '11 at 19:23

score 1 · Answer 1 · answered Aug 30 '11 at 20:45

1

Think about the powerset of {1, 2, 3}. We can think of it as a combination of:

{}  
{1} + powerset {2, 3}  
{2} + powerset {3}  
{3} + powerset {}

Taking the line {1} + powerset {2, 3}, this expands to:

{1} + { {}, {2}, {3}, {2, 3} }

which in turn becomes:

{ {1}, {1, 2}, {1, 3}, {1, 2, 3} }

The code is doing the same, using recursion to generate the smaller powersets and accumulating each set in a list.

answered Aug 30 '11 at 20:45

rossum

15,344
1
24
38

@Burleigh Bear What about it? Further expanding {2, 3} just leads to duplicates of {1}, {1, 2} and {1, 3} – rossum Aug 30 '11 at 20:54
Hmm, I think I didn't really understand your explanation. I thought that you were trying to show the working for Pow({1, 2, 3}). But your working never actually shows the answer? – Burleigh Bear Aug 30 '11 at 20:56
@Burleigh Bear: I don't show the full answer. I just explained the working at top level and took one part of the top level down to the second level. {2, 3} is one of the results of `{2} + powerset {3}` which I didn't expand. – rossum Aug 30 '11 at 21:36

Algorithm to find powerset of {1,2,3}

1 Answers1