Understanding recursive call in slicing array into sub-arrays

Question

I found this java code snippet to slice the array into all it's sub sets. But I'm not able to follow how the recursive calls work and how the subsets are formed. An explanation for the set {1,2,3} would be really helpful. Thanks in advance!

public static Set<Set<Integer>> powerSet(Set<Integer> originalSet) {

    Set<Set<Integer>> sets = new HashSet<Set<Integer>>(); //All the subsets will be stored in sets. 
    if (originalSet.isEmpty()) {
        sets.add(new HashSet<Integer>());
        return sets;
    }
    List<Integer> list = new ArrayList<Integer>(originalSet);
    int head = list.get(0);
    Set<Integer> rest = new HashSet<Integer>(list.subList(1, list.size()));
    for (Set<Integer> set : powerSet(rest)) {
        Set<Integer> newSet = new HashSet<Integer>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
    }
    return sets;
}

sets itself is a set and it contains {{1},{1,2},{1,3},{2,3},{2},{3},{1,2,3},{}} after the code finishes executing.

Eli Rose · Accepted Answer · 2014-05-12 04:37:22Z

What this is doing could be described this way.

If originalSet is empty, then return {} (since the empty set's only subset is the empty set).
Split originalSet into the first element (head) and all the others (rest).
We're keeping a running collection (sets) that will eventually be our answer. For every subset of originalSet that doesn't contain the first element (subsets of rest), put both it and a set which has all its elements plus head into our collection.

Example for {1, 2, 3}:

We want to find the power set of {1, 2, 3}.
    In order to do this, we take off 1 and find the power set of {2, 3}.
        In order to do this, we take off 2 and find the power set of {3}.
            In order to do this, we take off 3 and find the power set of {}.
                Which is {}.
            For everything above ({}), copy it over, then copy it over but add a 3.
            We have {{}, {3}}.
        For everything above ({}, {3}), copy it over, then copy it over but add a 2.
        We have {{}, {3}, {2}, {2, 3}}.
    For everything above ({}, {3}, {2}, {2, 3}), copy it over, then copy it over but add a 1.
    We have {{}, {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}}.

Note that there should always be 2^n elements, where n is the size of the original set.

Collectives™ on Stack Overflow

Understanding recursive call in slicing array into sub-arrays

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related