"a Power Set is the set of all sets of a certain set S"
what the hell does this means :D :D
let's see an example ,
for the set of numbers S = { 0, 1 , 2 , 3 , 4 , 5 }
isn't s_01 = { 0, 1, 2, 3 } is a subset of set S ?
and s_02 = { 2, 4, 5 } is a subset of set S ?
and s_03 = { 0 } is a subset of set S ?
we also define two special subsets those are:-
set s_00 = { } which is a null set or empty set.
and s_S = { 0, 1 , 2, 3, 4, 5 } that is the full set itself to be subsets of the original set.
the power set is defined to be the set of all those subsets.
that can be defined for the set S = { 7, 8, 9 }
P( S ) = { {}, {7}, {8}, {9}, {7,8}, {8,9}, {7,9}, {7, 8, 9} }
when it comes to intuition, we can generate all possible sets for a small number of S like 3 elements or possibly four.
but when it comes to large numbers (relatively) like 16 elements the no of subsets is 2^16 = 65536.
in this case : of course it will be impossible to generate all sets by direct intuition, instead we need a method to map this method, or more particularly an algorithm to compute for us all possible subsets.
let's see the following approach ;
we would think of the Set S = { 1 , 2 , 3 , 4 } as an example
may be some samples subsets will be the following
set 1 :
- we will take the 1
- we will not take the 2
- we will take the 3
- we will take the 4
doesn't this interpretation yields the set { 1, 3, 4 } ?
set 2 :
- we will not take the 1
- we will take the 2
- we will not take the 3
- we will not take the 4
and this yields the set { 2 }.
another way to represent this interpretation by the following string { 0, 1, 0, 0 }
- where a 0 represents that we will not take the indexed element
- and a 1 represent that we will take it in our consideration.
well here comes more clarification for the 2^n line we didn't get at the beginning.
if we are going to represent every set as a string where every single item is marked as taken or not.
so the no of ways we can represent this string is (2)*(2) *.....(2)*(2) n times = 2^n.
so all we have to now is to represent all numbers from 0 to 2^n -1 in binary representation
and then mask this representation into our set to decide weather to take a specific element or not :).
so we begin with a for loop that loops from 0 to 2^n -1
and through the loop we mask the current number in binary representation and check weather each element in this index exists or not.
a sample code is available here with some modifications.
and this is the puzzle of today ;) ;) whoever can break this encrypted code will have a prize ;) ;) and that itself is a surprise :)
and i am talking seriously :)
this algorithm runs in O( n *(2 ^ n) ) and that's all i can get so far .
any body has a faster algorithm ??
however, i beleive the ( 2 ^ n ) factor cannot be reduced because it is the no of subsets so it can be reduced than that to generate all possible case.
so anybody can generate something less than the ( n ) factor ?
