# Powerset algorithm

Tyler Long

Greenhorn

Posts: 4

posted 9 years ago

Hi,

Welcome to JavaRanch!

Let's say there are N elements in the set. The powerset of a set contains 2^N elements, so a 32-element set gives rise to a 4-billion element powerset.

Now imagine an N-bit integer. Let each bit in the number represent one specific element

So to print the powerset, you use either a real integer or long, or an array of booleans or any other representation you like of an integer. Then you "count", one value at a time, and for each value of the integer, you compute the corresponding element

Welcome to JavaRanch!

Let's say there are N elements in the set. The powerset of a set contains 2^N elements, so a 32-element set gives rise to a 4-billion element powerset.

Now imagine an N-bit integer. Let each bit in the number represent one specific element

**e**in the original set. There is one element**E**in the powerset for each value this integer can take. For each value of the integer, the 1-bits correspond to the elements**e**of the original set that belong to this powerset element**E**, and the 0-bits corresponds to elements not in**E**.So to print the powerset, you use either a real integer or long, or an array of booleans or any other representation you like of an integer. Then you "count", one value at a time, and for each value of the integer, you compute the corresponding element

**E**of the powerset and print it.
Tyler Long

Greenhorn

Posts: 4

posted 9 years ago

I do not understand this.

Thanks for the help anyway.

Originally posted by Ernest Friedman-Hill:

Hi,

Welcome to JavaRanch!

Let's say there are N elements in the set. The powerset of a set contains 2^N elements, so a 32-element set gives rise to a 4-billion element powerset.

Now imagine an N-bit integer. Let each bit in the number represent one specific elementein the original set. There is one elementEin the powerset for each value this integer can take. For each value of the integer, the 1-bits correspond to the elementseof the original set that belong to this powerset elementE, and the 0-bits corresponds to elements not inE.

So to print the powerset, you use either a real integer or long, or an array of booleans or any other representation you like of an integer. Then you "count", one value at a time, and for each value of the integer, you compute the corresponding elementEof the powerset and print it.

I do not understand this.

Thanks for the help anyway.

David McCombs

Ranch Hand

Posts: 212

posted 9 years ago

what Ernest is saying is that you can use the bits in an integer (or long) as "flags" for whether or not to include an element. say you have 3 elements.

2 ^ 3 = 8.

so, you need to count from 0 - 7 (giving you the 8 powerset elements).

as you count, you look at which bits in your counter are on. so when you get to say 3, your counter looks like this:

000000...000011 (the exact number of 0's depends on your use of an int vs. a long, but it doesn't matter).

so, from this, you know to include the 1st and the 2nd elements of the original set ( the set called

2 ^ 3 = 8.

so, you need to count from 0 - 7 (giving you the 8 powerset elements).

as you count, you look at which bits in your counter are on. so when you get to say 3, your counter looks like this:

000000...000011 (the exact number of 0's depends on your use of an int vs. a long, but it doesn't matter).

so, from this, you know to include the 1st and the 2nd elements of the original set ( the set called

**e**) as the elements of one of your powerset (**E**elements.There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Tyler Long

Greenhorn

Posts: 4