Teju's posting

Okay, i will also try :-)))
But i have not algorithmised the whole thing.

The signature of the BlackBox Algorithm is this,

subet_list BlackBox (SuperSet S, subset_list M)
So, the algo returns a subset_list such that the return value
satisfies the constraint mentioned.

Now, let us take an example.

Suppose the SuperSet S is as follows:-

S={1,2,3,4,5,6,7,8,9}

and M contains subsets...


{1,2,3,4,5} {6,7,8,9} ---->(1)
{1,2,3} {4,5} {6,7} {8,9} ---->(2)
{1,2} {3,4,5} {6,7,8} {9} ----->(3)
{1,2,3,4,5} {6} {7,8,9} ------>(4)


There are other subsets too in M.
However, as far as BlackBox algorithm is concerned
we will concentrate on these subsets.

So the blackbox algorithm is however always returning
the subset_list labelled (1) in the code when ALL these
subsets are there.

So the trick is this...

Let k = 3.
Then we want the answer (4) to be displayed.



1. call BlackBox(S,M).If the algorithm returns NULL, then goto
step 6.

2. You get a subset_string M1 //in our case we got (1)

3. Check the number of sets in M1.If it is "k" then stop
and return success.

4. Otherwise store M1 in a backup vector backup_vector
This is a vector of subset_string

5. Goto step1.

6. The Blackbox algorithm returned NULL.
This may have two implications :-
6a) There is no subset_string with k-elements satisfying the constraint.
6b) There is a subset_string with k-elements however, it contains one or
more subsets which we subtracted during the looping process.
This implication is reached for the scenario , i have mentioned.
Wherein, the subset {1,2,3,4,5} got subtracted initially, but actually
it is neededfor k=3 scenario.

7. Traverse through the backup_vector and keep on adding it to
M and call the Blackbox algorithm.
The details of the traversal has to be explained using pen and paper
and i cant put it here :-)