This week's book giveaway is in the Servlets forum.
We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line!
See this thread for details.
The moose likes Java in General and the fly likes How do i get all subsets? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "How do i get all subsets?" Watch "How do i get all subsets?" New topic
Author

How do i get all subsets?

Charlie Goth
Ranch Hand

Joined: Feb 26, 2004
Posts: 60
Is there a way of getting all subsets from a Set? I've tried writing it myself but its doing me head in, and making me think I'm not cut out for this programming

Any help would be greatly appreciated.


SCJP (77%)
Stefan Krompass
Ranch Hand

Joined: Apr 29, 2004
Posts: 75
Hi,

are you sure you need the power set of a set? Be aware that the power set will get huge very quickly. For a set with more than 20 to 30 entires, it will definitely not be representable with any normal Java data structure, and you'll run out of memory long, long before then.
But if you're sure that you need the power set, you might try it with recursion...

Stefan
Charlie Goth
Ranch Hand

Joined: Feb 26, 2004
Posts: 60
Yes I need it, its for calculating the winnings of 'canadian' style bets, that is bets on A, B, C, AB, AC, BC & ABC.
Michael Dunn
Ranch Hand

Joined: Jun 09, 2003
Posts: 4632
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
If you're willing to use iteration here's a technique that often works nicely:

There is a correspondence between binary numbers and subsets of a given set. Suppose I have a set of things {A, B, C}. I'll say that the subset {A, B, C} corresponds to the binary number 111, {A, C} corresponds to 101, {} corresponds to 000. If I've got an ordering of the items I can just say that a 1 means the item is in a set and 0 means it isn't simple enough.

Now if we want to iterate through all subsets of {A, B, C} we can just count the numbers from 000 to 111. Here's what the code might look like (I haven't tested it, so assume there are bugs):


[ August 08, 2004: Message edited by: David Weitzman ]
 
Don't get me started about those stupid light bulbs.
 
subject: How do i get all subsets?
 
Similar Threads
Generating all subsets of a Treeset
Is there a limit on the number of sql statements in a single transaction?
i got a different resolt than i was supposed to
Sets (Universal, Subsets, Union)
iterate through a hashMap