Tutorial Generating Power Sets by Counting in Binary - Printable Version

Tutorial Generating Power Sets by Counting in Binary - Printable Version

+- Sinisterly (https://sinister.li)
+-- Forum: Coding (https://sinister.li/Forum-Coding)
+--- Forum: Coding (https://sinister.li/Forum-Coding--71)
+--- Thread: Tutorial Generating Power Sets by Counting in Binary (/Thread-Tutorial-Generating-Power-Sets-by-Counting-in-Binary)

Generating Power Sets by Counting in Binary - Dong - 01-30-2015

Hello members of Sinisterly. I'm no expert programmer or mathematician, but I thought this would be a fun topic to share as I've noticed some people have difficulty grasping this concept in programming and discrete mathematics. This is my first tutorial, so hopefully my methods of explaining aren't all that confusing.

My Assumptions

You've programmed before
You understand some basic set theory
You understand the base-2/binary numeral system

The Problem
We are provided with a set S. Generate the power set P(S).

Now, there are several ways that one can go about solving this problem. However, the solution that I'll be detailing in this post is one I refer to as the "binary counting" method (can't think of a better name). Before we go into how this would actually be written in code, we're going to break the problem down a little bit and analyze it.

What is a "power set"?
Simply put, the power set of a set S is the set of all subsets of S (including the empty set and S itself).
Reference: Power set (Wikipedia)

To give you a better idea of what this means, I'll attempt to illustrate it:

Code:
S = { a, b, c }
P(S) = { {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }

Solving by Counting in Binary
So I'm not very sure how this method came about but I'm guessing that one day someone just looked at this and said "Hey, this looks really similar to counting in base 2!". It's definitely a creative solution and not the first that would have come to my mind.

Think about it: let's say we have a set of 3 elements S = {a, b, c}. The largest integer that can be represented in 3 bits is 7. So let's see what counting to 7 looks like in binary...

Code:
000
001
010
011
100
101
110
111
(Doesn't this look a lot like a power set?)

Let's imagine that each bit represents an element in our set S. So the rightmost bit represents 'a', the second bit represents 'b' and the leftmost bit represents 'c'. If a bit is set then it is a member of the subset, else it isn't a member of the subset.

Code:
= {}
= {a}
= {b}
= {a, b}
= {c}
= {a, c}
= {b, c}
= {a, b, c}

Solution

Remember these:

Code:
S = original set
P = power set
n = number of elements in S
2^n = number of subsets in P

So from what we can see, we'd need to implement some sort of counter within a loop for the binary counting. In order to determine our counter's maximum value, we'll need to calculate how many subsets will be generated based upon the number of elements n in S.

As a general rule, for now, we'll say that a set of n elements has 2^n subsets. I would go more into depth about why this is so, but this isn't a lesson on basic set theory. Google can definitely help you out here.
Reference: Subset (Wolfram)

Basically, we'll need a loop that maintains an index for each generated subset. Inside of that loop, we'll need another loop that maintains an index to represent each element in the original set S. This is necessary so that we can check which elements are to be included in the subset.

Some pseudocode with an explanation:

Code:
Vars: set[], set_size        // original set and number of elements in it

STEP 1: Determine number of sets in power set. 
             power_set_size = 2^(set_size)

STEP 2: Loop i from 0 to power_set_size

STEP 3: Loop j from 0 to set_size 
             Check if j'th bit is set in i

Example with set S = {1, 2, 3}:
There are 3 elements in the set S. Therefore the power set P will consist of 2^3 subsets.
Let's say we're at the point where i = 3. Since we're using i as our index for the subsets of P, we are now looking at the third subset. 
Let's convert 3 to binary => 011
In the second loop, we'll use the index j, which represents an element of the original set S, to check which bits are set in i. This will allow us to determine which elements belong in the subset.

What happens:
(Is the j'th bit set in i?)
Is the first bit set in 3 (011)? Yes, so add the first element of S to the 3rd subset of P.
Is the second bit set in 3 (011)? Yes, so add the second element of S to the 3rd subset of P.
Is the third bit set in 3 (011)? No, do nothing.

Conclusion
Hopefully this helps some of you out. This can be a useful concept to understand especially when you're studying topics such as algorithms and discrete mathematics.

I'll post my solution below. Please give me your feedback and definitely go ahead and submit your own solutions so I can add them to the thread. You can go about this another method if you like; I'd be very interested in seeing the code.

C Solution (I may write up a generic C++ solution soon)

Spoiler:Code:
// generates the powerset of a provided set.
void powerset(char *set, size_t *set_size, char **powerset, size_t *powerset_size){
        for (size_t i=0; i<*powerset_size; i++){
                for (size_t j=0; j<*set_size; j++){
                        if (i & (1<<j)){
                                powerset[i][j] = set[j];
                        }
                }
        }
}


If you don't understand what's going on in this line: 
Quote:if (i & (1<<j)){
Spoiler:
This line executes a bitwise AND operation on i and (1<<j). (1<<j) is another bitwise operation which is called a "left shift". 

Let's say we have an operation (3 << 2). This will take the bits in the number 3 and shift them 2 places to the left.
Code:
00000011 << 2 = 00001100


So basically what we're doing in the code is shifting all of the bits in the integer 1 (001 in base 2) to the left by j places. We're then using this in a bitwise AND operation in order to check if the j'th bit is set.

Code:
A    B    A & B
1    1    1
1    0    0
0    1    0
0    0    0


The AND operation will only return a non-zero value if two bits are set.

Let's say we're running the operation (3 & (1 << 1)).

Code:
00000011
00000010
----------------
00000010
----------------

Therefore, a non-zero value is returned. The 2nd bit is set.

RE: Generating Power Sets by Counting in Binary - Satan - 01-31-2015

Pretty nicely written, if a sort of spoonfeeding. I'd like to see more out of you.

RE: Generating Power Sets by Counting in Binary - Dong - 01-31-2015

(01-31-2015, 05:30 AM)Six Wrote: Pretty nicely written, if a sort of spoonfeeding. I'd like to see more out of you.

Thanks. I guess I have a tendency to be too thorough when I explain things. I'll come out with something a little different soon.

RE: Generating Power Sets by Counting in Binary - Eclipse - 01-31-2015

Pretty well written guide. Interesting too, I wouldn't have thought of that method. I'm looking forward to your next one.

RE: Generating Power Sets by Counting in Binary - Blunt - 01-31-2015

Finally got around to reading this and it is quite interesting, +1 for the thread and hope you make some more!!