# How do i get all subsets?

Charlie Goth

Ranch Hand

Posts: 60

Stefan Krompass

Ranch Hand

Posts: 75

posted 12 years ago

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

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

David Weitzman

Ranch Hand

Posts: 1365

posted 12 years ago

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 ]

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 ]