Power Set Algorithm

Sekky · 2007-03-22 12:53:24

I'm having problems coming up with an algorithm to produce the power set of a given finite set, I think I'm starting to see why power set is an axiom, I'm guessing it can be done recursively but I'm having trouble figuring it out on paper, any pointers or pseudocode? I'm coding in standard OOP.

MathsIsFun · 2007-03-22 13:52:36

Like this one? Power Set Maker

Maybe Power Set will help

Ricky · 2007-03-22 14:40:07

Here is my java code. Ugly, but I believe it works. Ever since I wrote this, I wanted to find a more elegant way. Have yet to try though. If you don't know java, I can translate into pseudo code. I'd just rather not if I don't have to.

Edit:

And there are some debugging statements, just ignore those.

Class declaration:

public class Set {
  ArrayList elements;

Function:

public Set powerset() {

    ArrayList result = new ArrayList();
    result.add(new Set()); //null set
    
    int i, j, k;
    for (i = 1; i < elements.size(); i++) {
      int indexes[] = new int[i];
      for (j = 0; j < i; j++) {
        indexes[j] = j;
      }
      while (indexes[0] <= elements.size() - i) {
        //Construct a set to add and add it
        Set s = new Set();
        System.out.print("Adding: ");
        for (k = 0; k < i; k++) {
          System.out.print(indexes[k] + " ");
          s.add((Element)elements.get(indexes[k]));
        }
        System.out.println();
        result.add(s);

        //increment the indexes
        //indexes[i-1]++;
        for (k = i-1; k >= 0; k--) {
          if (indexes[k]+1 < elements.size() - (i-1 - k)) {
            break;
          }
        }
        if (k < 0) break;
        indexes[k]++;
        for (k++; k < i; k++) {
          indexes[k] = indexes[k-1]+1;
        }
      }
    }

    return new Set(result);
  }

Sekky · 2007-03-22 14:50:54

Maybe it's just late but I'm having trouble reading the java, not that I even know java...

Don't stress over pseudocode, a description of the algorithm should be enough, if you could explain how it's done I should be able to implement it.

MathsIsFun · 2007-03-22 17:49:58

Sekky wrote:

MathsIsFun wrote:
Maybe Power Set will help
Don't patronise me, of course that doesn't help.

You think I was patronising you? On the contrary I thought you would say "of course!" Don't mistake my style of presentation for idiocy, the section "It's Binary!" shows the algorithm I used.

Just increment a counter from 0 to 2[sup]n[/sup]-1 and each time examine its bits. If the bit is 1, then include the matching element in the subset. All explained on the page.

Powerset of {a,b}:

0 => 0 => {}
1 => 1 => {b}
2 => 10 => {a}
3 => 11 => {a,b}

I don't wish to patronise you further.

Ricky · 2007-03-22 19:00:15

Wow MathIsFun... great algorithm. It's one of those, "I should have thought of that" moments for me.

Asad Paki · 2009-02-02 19:57:46

Wow This Is A Freaking Amazing Algorithm Dude!!!! Thanks Alot

George,Y · 2009-02-03 16:51:15

It is actually very standard.

By the way, I wonder why they cannot count real numbers between 0 and 1 in binary digitals by power set?

{};0;
{1};0.1;
{2}, {1,2}; 0.01,0.11;
{3}, {1,3}, {2,3}, {1,2,3};0.001,0.101,0.011,0.111;
...; ...

The above shows real numbers between 0 and 1 are definitely countable, all the real numbers are countable as well if we plug in inversions.

Last edited by George,Y (2009-02-03 16:53:01)

George,Y · 2009-02-03 17:09:20

One easy way to generate a power set of a set of n elements is simply

list 0,1,...2^n-1

and then transfer them from mod 10 to mod 2
0,1,10,...,11(n)1

and then translate the binary sequence as turn on's for each element
0 is null, 1 is only the first element is in, 10 is the second one in, other excluded, ... the last is all in.

Ricky · 2009-02-03 17:30:28

The above shows real numbers between 0 and 1 are definitely countable

You can't express 0.1 in a finite number of binary digits. You won't even get all the rational numbers, let alone all the real numbers.

George,Y · 2009-02-04 03:55:13

1/10= (1/8)(1/2+3/10) = 1/16+(1/8)(1/2)(1/2+1/10) = 1/16+1/32+(1/16)(1/10) =...

By this algorithm, 1/10 in binary can be approximated by
0.00011 0011 0011 recurring
And frankly this is what you can get from strict logic proof of induction, Ricky.

My method can also go over
0, 0.0, 0.00, 0.000, 0.0001, 0.00011, 0.000110, ...

ENDLESSLY

As long as my method reaches the digitals you reached, you can say it is slower, but you cannot say it doesn't mean the same thing

TheDude · 2009-02-04 04:11:33

I think there's a misunderstanding. George, where you said that the real numbers are countable with a binary powerset, I think you meant that they are expressable. Countability implies a 1-1 relationship between the set in question (in our case, the reals) and the natural numbers.

George,Y · 2009-02-04 04:21:21

I think there is misunderstanding that real numbers are already steady thing, dude. Actually, how many pi's decimals can be reached is refreshing but yet not arriving at infinite. As long as my method can peg with the decimals we reach so far for any real number, in a way it has count all the reals we know, or the knowable part of reals.

TheDude · 2009-02-04 04:35:27

I'm not sure what you're saying. Are you saying that we can express as many digits of pi in binary as we can in decimal? If so then you're right. Although it will take many more digits we can express pi to the same accuracy in binary that we can in decimal.

However, countability is a whole different subject that deals with the size of infinite sets like the naturals, the rationals, and the reals.

George,Y · 2009-02-04 04:47:14

Yes I do mean that. So far reals include two parts, one real, one imaginary.

The real part is the recurring, and the approximated non-recurring, or the finite growing series.
The imaginary part is the claim that it does contain infinite decimals already, or that we can have all of the series and group it as a set.

3, 3.14, 3.141, 3.1415, ...
is what we did find and what we can continue improving

{3, 3.14, 3.141, 3.1415, ...} (the whole of the series)
is exaggeration, which is not proved.
Unfortunately, real definition is the latter.

Last edited by George,Y (2009-02-04 04:52:07)

TheDude · 2009-02-04 05:24:18

I'm sorry, I don't understand what you're saying. Do you mean that we haven't proven that pi's digits never get to the point that they repeat indefinitely?

luca-deltodesco · 2009-02-04 05:26:25

You seem to be saying that we havn't proved pi is irrational george?

George,Y · 2009-02-04 05:42:10

that they repeat indefinitely?

Yes indefinite.

But not infinite.

These two are different.
How different? Back to my previous post, the former indefinite, the latter infinite.

TheDude · 2009-02-04 05:54:34

So are you saying that pi's digits do not go on infinitely, or that we haven't proven it?

LuisRodg · 2009-02-04 06:23:58

The reals are countable? Go look at Cantor's Diagonal Argument and come back to this thread.

Like "TheDude" said, countability requires a bijection from said set to the natural numbers. Unless of course you have another notion of countability, in which case, its useless arguing.

Last edited by LuisRodg (2009-02-04 06:44:50)

George,Y · 2009-02-04 07:27:37

So are you saying that pi's digits do not go on infinitely, or that we haven't proven it?

go on is "indefinite", you get 1 decimal, 2 decimals, 3,..., but you haven't achieved "all" the decimals by the process of "going on".

To claim you can go on means you have already infinite decimals at hand is simply hasty generalization.

About diagonal argument, do you mean 0.d1d2d3...?

I really miss the point what he wanted to prove.

Last edited by George,Y (2009-02-04 07:33:54)

TheDude · 2009-02-04 07:30:40

No, we will never know all of the digits of pi. That doesn't mean that they aren't there, though.

George,Y · 2009-02-04 07:40:09

That doesn't mean that they aren't there, though

How do you find they are there? Prove it.

TheDude · 2009-02-04 07:45:50

http://en.wikipedia.org/wiki/Proof_that_%CF%80_is_irrational

George,Y · 2009-02-04 08:03:48

It's a proof that pi is not a rational number or a fraction of two integers. However, it is not a proof that pi exists. You have to add in existential assumption to believe it exists.

This is also a reply to luca.

Math Is Fun Forum

#1 2007-03-22 12:53:24

Power Set Algorithm

#2 2007-03-22 13:52:36

Re: Power Set Algorithm

#3 2007-03-22 14:40:07

Re: Power Set Algorithm

#4 2007-03-22 14:50:54

Re: Power Set Algorithm

#5 2007-03-22 17:49:58

Re: Power Set Algorithm

#6 2007-03-22 19:00:15

Re: Power Set Algorithm

#7 2009-02-02 19:57:46

Re: Power Set Algorithm

#8 2009-02-03 16:51:15

Re: Power Set Algorithm

#9 2009-02-03 17:09:20

Re: Power Set Algorithm

#10 2009-02-03 17:30:28

Re: Power Set Algorithm

#11 2009-02-04 03:55:13

Re: Power Set Algorithm

#12 2009-02-04 04:11:33

Re: Power Set Algorithm

#13 2009-02-04 04:21:21

Re: Power Set Algorithm

#14 2009-02-04 04:35:27

Re: Power Set Algorithm

#15 2009-02-04 04:47:14

Re: Power Set Algorithm

#16 2009-02-04 05:24:18

Re: Power Set Algorithm

#17 2009-02-04 05:26:25

Re: Power Set Algorithm

#18 2009-02-04 05:42:10

Re: Power Set Algorithm

#19 2009-02-04 05:54:34

Re: Power Set Algorithm

#20 2009-02-04 06:23:58

Re: Power Set Algorithm

#21 2009-02-04 07:27:37

Re: Power Set Algorithm

#22 2009-02-04 07:30:40

Re: Power Set Algorithm

#23 2009-02-04 07:40:09

Re: Power Set Algorithm

#24 2009-02-04 07:45:50

Re: Power Set Algorithm

#25 2009-02-04 08:03:48

Re: Power Set Algorithm

Board footer