# Algorithm for computing power sets

• Oct 18th 2007, 05:09 AM
Eclyps19
Algorithm for computing power sets
I am not positive if this is on the right topic, let alone the right website, but I'll give it a shot.

I'm writing a computer program that computes sets. I have a basic computation that calculates the power sets with any number of elements. Part of the algorithm looks something like this

Quote:

for i = 0 to the number of elements - 1
for j = i + 1 to the number of elements - 1
output the the element with the index of i and the element with the index of j
I know it's rough, and not complete as it doesn't output all the elements, but I don't have the code in front of me right now. Anyways, it's kind of irrelevant.

What I need to figure out, now, is how to calculate the power set of a power set of a power set. If any of you can help me figure out an algorithm (probably using loops) that'd be great. If not, no big deal. This isn't a programming forum :)

Thanks for the help
• Oct 18th 2007, 06:59 AM
Plato
Quote:

Originally Posted by Eclyps19
I'm writing a computer program that computes sets. I have a basic computation that calculates the power sets with any number of elements.

As is often the case this turns out to be more of a mathematical problem than a programming problem. Although it has been at least ten years since I have done any real programming, I can give some mathematical help.

It is the case that all you must do is to list all the possible bit-strings of length n. Each such string represents one subset of a set of n elements. The attached pdf file will give you the rational for that.

I can give you the code that I use to generate a table of these strings using a very elementary CAS.
It is:
$\begin{array}{l}
N: = 8,\quad j: = 1 \ldots 2^N ,\quad k: = 1 \ldots N \\
T_{j,N + 1 - k} : = \bmod \left[ {ceil\left( {\frac{j}{{2^{k - 1} }}} \right),2} \right] \\
\end{array}$

This produces all 8-bit strings. Change the value of N to produce all N-bit strings.