Results 1 to 2 of 2

Math Help - Algorithm for computing power sets

  1. #1
    Newbie
    Joined
    Oct 2007
    Posts
    14

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,965
    Thanks
    1784
    Awards
    1
    Quote Originally Posted by Eclyps19 View Post
    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}<br />
 N: = 8,\quad j: = 1 \ldots 2^N ,\quad k: = 1 \ldots N \\ <br />
 T_{j,N + 1 - k} : = \bmod \left[ {ceil\left( {\frac{j}{{2^{k - 1} }}} \right),2} \right] \\ <br />
 \end{array}
    This produces all 8-bit strings. Change the value of N to produce all N-bit strings.
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Computing Powers of Sets
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: November 14th 2011, 08:43 AM
  2. [SOLVED] Cardinality of Sets and Power Sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 8th 2011, 06:26 PM
  3. [SOLVED] O(Log(n)) Algorithm for Computing Fibonacci Numbers, SICP Ex. 1.19
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 9th 2011, 11:55 AM
  4. computing a power
    Posted in the Calculus Forum
    Replies: 1
    Last Post: January 15th 2010, 09:59 AM
  5. computing sets
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 24th 2009, 05:09 PM

Search Tags


/mathhelpforum @mathhelpforum