Safely Working with Sets of Sets -- Producing a PowerSet

[Jesse Silverman]

The definition of a PowerSet is a set of all subsets of the original set given, from the Null Set [] right up to and including the full set given as input.
For { "A", "B", "C" ] that would be: [ [], ["A"], ["B"], ["C"], ["A", "B"], ["B", "C"], ["A", "C"], ["A", "B", "C"] ] where we don't care about the order of either the elements in each subset or the order of the subsets.

I spazzed out on an interview and didn't get it in time, then I spent about an hour coming up with this solution and another hour cleaning it up to not look stupid or unreadable, as I was still somewhat confused while getting it working.  I chose the "To make a statue of an elephant, start with a really large block and chip away everything that doesn't look like an elephant" approach.

I am already braced for the "Count the dumb errors in the code" that will likely follow.
The point is to learn not to make them again.
"It seems to generate correct results and doesn't take a whole lot of lines" is the best I can say for it for sure.

package org.jessesilverman.powerset;
import java.util.Set;
import java.util.HashSet;
public class PowerSet {
	
	public static Set< Set<String> > powerSet(Set<String> startingSet)
	{
		startingSet = Set.copyOf(startingSet);	// nobody said it is okay to mess with the Set they lent us....
		//boolean chatty = true;
		boolean chatty = false;
		
		Set< Set<String> > answer = new HashSet<>();
		answer.add( startingSet );
		
		int loopCount = 0;
		int addCount = 0;

		Set< Set<String> > prev = new HashSet<>( );
		prev.add( startingSet );

		while (prev.size() > 0)
		{
			// compute and add all sets with (n-1) members each using each of the sets
			// containing (n) members each from last round or initial condition.
			// Try adding reduced set with each element in prior fuller set removed
			// in turn.  Add if not there already.
			if (chatty)
			System.out.println("Adding diminished sets from the " + (prev.size() )
					+ " sets of sets added last iteration." );
			Set< Set<String> > next = new HashSet<>();
			for( Set<String> priorMember : prev ) // for each member set added last round
			{
				if (chatty)
					System.out.println("Considering prior set: " + priorMember);
				// for each element of that set form smaller set with element removed
				for( String el : priorMember)
				{
					if (chatty)
						System.out.println("Removing element: " + el);
					++loopCount;
					Set<String> modifiablePrior = new HashSet<>( priorMember );
					modifiablePrior.remove( el );
					if (chatty)
						System.out.println("Minus that element yields: " + modifiablePrior );

					if (!next.contains( modifiablePrior ) )	// really just optimization
					{
						++addCount;	// creating the set is kinda expensive...
						Set<String> toAdd = new HashSet<>(modifiablePrior);
						next.add( toAdd );
						answer.add( toAdd );
					}

				}	// for each element in priorMember
			}	//  for each set from last round

			prev = next;	// round over, the student becomes the master!
		}
		System.out.println("Total nested loop passes: " + loopCount);
		System.out.println("Total subsets added in loops: " + addCount);
		return answer;
	}
	
	public static void main(String... arrrggh)
	{

		System.out.println("Putative PowerSet Program");
		Set<String> originalSet = new HashSet<String>();
		originalSet.add("A");
		originalSet.add("B");
		originalSet.add("C");
		originalSet.add("D");
		//originalSet.add("E");
		//originalSet.add("F");
		//originalSet.add("G");
		System.out.println("Computing PowerSet for Set:\n" + originalSet );
		Set< Set<String> > answer = powerSet( originalSet );
		
		System.out.println("Number of Sets in PowerSet: " + answer.size() );
		System.out.println("The answer is:\n" + answer);

		
	}

}

[Carey Brown]

I knew it had to have a recursive solution. Still, took a bit less than an hour to come up with it. There is probably a more efficient way to do this but this has very few lines of code.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class PermutationPowerSet
{
	public static void main( String[] args )
	{
		List<String> list = List.of( "A", "B", "C" );

		Set<Set<String>> sets = powerSet( list );

		System.out.println( sets );
	}

	private static Set<Set<String>> powerSet( List<String> list )
	{
		return powerSet( new HashSet<Set<String>>(), list );
	}

	private static Set<Set<String>> powerSet( Set<Set<String>> sets,
			List<String> list )
	{
		Set<String> newSet = new HashSet( list );

		if( sets.contains( newSet ) )
			return sets;

		sets.add( newSet );

		for( int i = 0 ; i < list.size() ; i++ )
		{
			List<String> newList = new ArrayList<>( list );
			newList.remove( i );
			powerSet( sets, newList );
		}
		return sets;
	}
}

[Paul Clapham]

How about this algorithm:

1. Start with a power-set which contains only the empty set.

2. For each element X in the original set:

 a. For each set S in the power-set, add the set S-union-[X] to the power-set.

I haven't tried writing that code and I'm not going to because I'm working on a different project now, but it doesn't look too difficult. Some care needs to be taken in the loop which adds the S-union-[X] sets so that it doesn't go into an infinite loop which tries to add more sets based on the sets that it added earlier in the loop.

EDIT: That was in response to the original post, not Carey's recursive solution. I'm not sure if my algorithm is the same as Carey's or not but I wouldn't call mine recursive.

[Jesse Silverman]

Hi Carey.
Back from University Maths, I always distinguished between Combination and Permutation thusly:
Permutation includes an order A, B, C != B, C, A
Combination doesn't include an order: A, B, C == C, B, A

Am I reading too much into the word permutation or missing a key feature of your solution?

[Jesse Silverman]

Paul:

My first thought was to try it that way, tho I was still keeping track of "rounds" where in each round I'd add increasingly larger sets based on augmenting the previous round's sets.

Somehow my brain saw the reduction/dimunition solution more clearly mid-way trying to code it...

It isn't clear to me if one scales better than the other, I stuck in the various counting variables there in case I wound up trying different versions to give some metrics besides stopwatch/wall-clock time.

[Paul Clapham]

Jesse Silverman wrote:Back from University Maths, I always distinguished between Combination and Permutation thusly:
Permutation includes an order A, B, C != B, C, A
Combination doesn't include an order: A, B, C == C, B, A

In Math, just as in Java, a "set" has no ordering. So perhaps "CombinationPowerSet" would have been more precise...

[Carey Brown]

Jesse Silverman wrote:Hi Carey.
Back from University Maths, I always distinguished between Combination and Permutation thusly:
Permutation includes an order A, B, C != B, C, A
Combination doesn't include an order: A, B, C == C, B, A

Am I reading too much into the word permutation or missing a key feature of your solution?

You're reading too much into that. I named it in such a way as I might have half a chance of finding it in the future. PowerSets don't hold any meaning for me.

[Stephan van Hulst]

Powersets were one of the first things I learned about in my Discrete Mathematics class back at uni. Here's how I would generate one:

static <T> Set<Set<T>> getPowersetOf(Collection<? extends T> elements) {
  if (elements == null)
    throw new IllegalArgumentException();

  if (elements.isEmpty())
    return Set.of(emptySet());

  var fewerElements = new HashSet<>(elements);
  var removedElement = elements.iterator().next();
  fewerElements.remove(removedElement);

  // Example: For elements { x, y, z } and removedElement z, smallerPowerset will be { {}, { x }, { y }, { x, y } } .
  Set<Set<T>> smallerPowerset = getPowersetOf(fewerElements);

  var powerset = new HashSet<>(smallerPowerset);

  // Example: Add z to each of the sets in smallerPowerset, and add the resulting sets to the final powerset.
  // { {}, { x }, { y }, { x, y } }  ∪  { { z }, { x, z }, { y, z }, { x, y, z } }
  for (var set: smallerPowerset) {
    var expandedSet = new HashSet<>(set);
    expandedSet.add(removedElement);
    powerset.add(expandedSet);
  }

  return powerset;
}

[Carey Brown]

Nice code Stephan. The thing that bothered me about mine was the need to call contains(), which yours doesn't need. Very good.

[Carey Brown]

Thanks for the cow Campbell !!

[Jesse Silverman]

Dang, Stephan:

Your solution is so compact and neat and robust and parameterized on <T> to boot!

My natural inclination is to dislike studying other people's solutions before not just trying something myself, but to get it working too.

Mine works, but this has several good practices that I missed.  I like the IllegalArgumentException and the use of:
if (elements.isEmpty())
   return Set.of(emptySet());

But I think the magic secret sauce that was preventing me from constructing a neat recursive solution, which may be totally obvious to someone who has worked more of these problems, but to me still looks genius is that the iterator is part of the Set, meaning that there is no loss of memory of "where we are up to" across the recursive calls.
Which is just obvious unless it is not, in which case it just looks brilliant:
 var removedElement = elements.iterator().next();

My Iterator novice brain gets confused if I don't see .hasNext() in a while loop around the .next() calls all in one place.

I think learning to get past that may lead me to neat recursive solutions for many problems.

Even in so few lines, it reads like a tutorial presentation that can be compiled and executed, perhaps stepped thru, for maximum learning potential.

Carey's is good too.  I wasn't expecting to see a List<> anywhere but I think that was another way to get around whatever was blocking me from coding the recursive solution.

[Jesse Silverman]

I see Carey made use of the List so he could use the List ability to remove by index.
I wanted to remove by index at one or more points in one or more of my solutions, but I didn't have a List, only a Set.
At least that mini-mystery is solved for me.

[Carey Brown]

Stephan's use of iterator was because the Collection had no "first()" method, and that was a substitute. I had to study that also.

Edit: I guess HashXXX really has no concept of 'first' so it is really 'get an' element from the Collection and we don't care where.

[Stephan van Hulst]

Aye, I used an iterator to get 'any' element from the set, not necessarily the first.

Jesse, if you want to see an interesting use of iterators during a recursion, I'll show you later how I generate a stream of permutations.

[Carey Brown]

Stephan van Hulst wrote:Jesse, if you want to see an interesting use of iterators during a recursion, I'll show you later how I generate a stream of permutations.

I'd be interested in seeing that also. Thanks.

[Mike Simmons]

Note that a powerset will have 2^N elements, each of length O(N).  That can be a lot of memory - so using a Set (or any Collection or array) may be a bad idea if the size is large enough; it kills your memory.  I favor using a Stream for this reason.  See my post in Java-8 Streams - creating a class with stream() method for some code for this.

[Jesse Silverman]

Mike:

That is why you are a Master Rancher!
Well, maybe not the reason, but a reason I consider it an appropriate title.

I have watched a bunch of videos about Streams and Collectors from Venkat Subramaniam, but I haven't gone thru the phase where I slog thru everything in writing, take copious notes, run lots of sample programs and everything else it takes before I am comfortable saying I know something.  I have most of the ideas, but few of the details yet come flying out of my fingertips at the keyboard.

I often felt like the first OCJP exam teaches you how to write classical 1995-2013 Java, and the second exam teaches you / tests you on NOT writing anything like that anymore.
Nearly no explicit for loops, using streams by default, etc.
Now that the tests are combined into one it is a bit weird.

I am definitely into seeing that streams solution.

I am heavily aware that 2^n can get pretty big pretty fast, the problem I failed then succeeded at did indeed ask us to materialize and return the whole Set<Set<> > at once.

Stephan:
Aye, I used an iterator to get 'any' element from the set, not necessarily the first.

Yeah, the iterator keeps getting you "elements you haven't used yet" which is slightly different from "any".
I knew what I wanted but didn't think of using an iterator attached to the set thru the recursive calls, and wound up doing an iterative solution all inside one method invocation.

I feel like once people had enhanced for( : ) the lazy ones just forgot about iterators, at least until Java 8 gave us Spliterators, which I am pretty sure are the greatest things since sliced anything.  The really lazy ones don't know how to leverage Spliterator, but that won't be me after I get thru my current studies.

Even before or leaving aside the new tools we have had since Java 8, I kept thinking that the people who were just forgetting about Iterator and ListIterator the moment they encountered for ( : ) were making a mistake, I found it hard to identify the places it would come in super-handy.  Your solution nicely showed one of them.

Thanks everyone.

My original anxiety about whether a Set< Set<T> > was automatically valid was based on not quite realizing that yes, HashSet overrrides equals(Object) and .hashCode(Object) just fine, so as long as you don't mess with any of the subsets after you've placed them, it is all good.  If you are afraid someone else will, you can always wrap them to be unmodifiable...

[Carey Brown]

Jesse Silverman wrote:Stephan:
Aye, I used an iterator to get 'any' element from the set, not necessarily the first.

Yeah, the iterator keeps getting you "elements you haven't used yet" which is slightly different from "any".

Well, yes, sort of. You get 'any' element and you also get a 'remaining' set. The next time round the recursion you get 'any' of the former 'remaining' which results in a new 'remaining'. The iterator though is a different iterator, not "the" iterator.