Win a copy of High Performance Python for Data Analytics this week in the Python forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Bear Bibeault
  • Liutauras Vilda
Sheriffs:
  • Jeanne Boyarsky
  • Tim Cooke
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Stephan van Hulst
  • Jj Roberts
  • Carey Brown
Bartenders:
  • salvin francis
  • Frits Walraven
  • Piet Souris

Safely Working with Sets of Sets -- Producing a PowerSet

 
Ranch Foreman
Posts: 175
8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.

 
Saloon Keeper
Posts: 7622
68
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Marshal
Posts: 26309
80
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Ranch Foreman
Posts: 175
8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Ranch Foreman
Posts: 175
8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 26309
80
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Saloon Keeper
Posts: 7622
68
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Saloon Keeper
Posts: 12628
273
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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:
 
Carey Brown
Saloon Keeper
Posts: 7622
68
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Saloon Keeper
Posts: 7622
68
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
 
Jesse Silverman
Ranch Foreman
Posts: 175
8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Ranch Foreman
Posts: 175
8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Saloon Keeper
Posts: 7622
68
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Saloon Keeper
Posts: 12628
273
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Saloon Keeper
Posts: 7622
68
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Master Rancher
Posts: 3761
49
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Ranch Foreman
Posts: 175
8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Saloon Keeper
Posts: 7622
68
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
a wee bit from the empire
the value of filler advertising in 2020
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic