Power Set - Generate All Sets from a Certain Set

"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 ?

SRM: 477 - DIV: II - 500 Problem - Islands

Trivial problem with normal iteration, you can view the problem here

the main idea is to count the no of beaches that each cell has - if it is a land piece-.

We define a beach as a land that has a side neighbouring a water cell.

we iterate through all cells, if the current cell is a land peice we call the function countBeaches(i , j)

that counts the no of peace surrounding the indexed cell [ i ] [ j ].

we can define the function countBeaches(i, j) with two ways ;

the first one is two construct nested if statements that checks for every condition that exist for the 8 possible directions ( North, North West, North East, South , South East, South West)

regarding of course the difference between the odd lines and the even lines.

see the following picture to notice the difference

but another way to do this is to construct an array with the delta positions and add them to the original indexes to make the affect of translation.

that of course saves lots of coding time.

SRM: 477 - DIV: II - 250 Problem - Vacation Time

The problem main idea was to choose an interval to ensure the minimum re-scheduled days through the whole No. of days given

You can view the whole problem here

The first approach to this problem is brute force algorithm, we may think of it this way;

may be we should try all the possible intervals that start at day no [ i ] and end at day [ j ]

and count the no of re-scheduled days between those days, and keep track of the minimum no of scheduled days.

This algorithm will satisfy the time limit but is still as obvious in O ( n ^ 2 ).

another Dynamic Solution will solve problem in only O( n ).

the hint is we may solve this problem as follows ;

1st - we will have an Array that holds at Position [ i ] ; the sum of all scheduled days from day [1] to day [ i ]. that is by simply looping through the array and accumlating the sum of the previous day to this day we are in.

2nd - we loop again through the same array checking the minimum scheduled days in between day[ i ] and day [ i + K ].

Simply we transformed the too nested loops into two separate loops that each run in O ( n ) (^.^)

No one believe what Dynamic Programming can do to your life :)

Here is the sample code for a more clarification.