but will work very well for k=1 and 2..may be this can be improved..

the idea is to sort the subsets based on their size..use hashing..and resolve collision by using link list..

now instead of storing the actual sets..store the sum of its elements..now the prob reduces to finding k sums(sets) such that their sum is equal

to the sum of universal set..

ex:

Say the main set is {1, 2, 3, 4, 5, 6, 7, 8, 9} and the 9 subsets given are

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

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

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

now grouping them based on their size

0 -> NULL -> 0

1 -> {8} {9} -> 8, 9

2 -> NULL -> 0

3 -> {1,2,3} {4,5,6} {7,8,9} {5,6,7} -> 6 , 15, 24, 18

4 -> {1,2,3,4} {6,7,8,9} -> 10, 30

5 -> {1,2,3,4,5} -> 15

the sum of the universal set is 45

now if k = 2, u take two indicies(i and j) , one for each end..now chk for the sum of their sizes..this should be equal to size of the universal set..

if not change one index as reqd..this chk is nothing but chking i+j = |universal set|. After u have found correct values for i and j search for

values within those lists such that the sum of these values = sum of universal set.

in our example

i = 0 , j= 5

i+j=5 < 9 (size of univ set)

so make i = 4

now chk for values within these two lists

15 + 10 = 25 != 45

chk for next comb

15 + 30 = 45

bingo....

if u store the values in the list in sorted order then u can apply the same logic of finding the indices to these lists as well...

this method of grouping subsets and then representing them by their sums will help cos of reduced num of comparisons...

now the main prob is to find out mCk combinations and exclude all combinations for which the sum of the selected k values != | univ set|

i leave this to the reader as exercise ;)

## No comments:

Post a Comment