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 :-)

## No comments:

Post a Comment