This week's book giveaway is in the Artificial Intelligence forum.
We're giving away four copies of Pragmatic AI and have Noah Gift on-line!
See this thread for details.
Win a copy of Pragmatic AI this week in the Artificial Intelligence 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:
  • Jeanne Boyarsky
  • Liutauras Vilda
  • Campbell Ritchie
  • Tim Cooke
  • Bear Bibeault
Sheriffs:
  • Paul Clapham
  • Junilu Lacar
  • Knute Snortum
Saloon Keepers:
  • Ron McLeod
  • Ganesh Patekar
  • Tim Moores
  • Pete Letkeman
  • Stephan van Hulst
Bartenders:
  • Carey Brown
  • Tim Holloway
  • Joe Ess

How do i get all subsets?  RSS feed

 
Ranch Hand
Posts: 60
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 60
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes I need it, its for calculating the winnings of 'canadian' style bets, that is bets on A, B, C, AB, AC, BC & ABC.
 
Ranch Hand
Posts: 4632
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
 
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!