# Thread: Algorithm for computing power sets

1. ## 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

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

2. 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:
$\displaystyle \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.