0

The question is completely contained in the title. I have a set B of sets {B1 .. Bn} and I need to obtain the smaller possible subset of B which sums up to a given set A (repetitions allowed).

I have thought of this approach:

1) index sets by the contained elements

eg. set B1 contains element a,b; set B2 contains b,c, the indexing will be something like 

a => B1
b => B1, B2
c =>     B2

Thus the aim changes to find the lesser number of columns which cover all elements.

2) get all the combinations of two elements. If one or more combinations have all the elements (if there is no element contained in a set that is not in the chosen columns) I'm done. Else collapse those combinations to a new set, keep track and keep iterating.

The problem is that I have to create a new data structure to collapse the sets in B. I need to understand if this is a correct approach in respect to time complexity, moreover I need to understand if there is a simpler way of implementing this approach.

Gabber
  • 5,152
  • 6
  • 35
  • 49
  • Your second approach have the disadvantage that if more than two `B` subsets are required a new approach should be used. The 1st approach seem more scalable. You don't provide any information about the size of the sets though – Eypros Jul 15 '14 at 09:13
  • Forgive me for not being clear. 1) and 2) are steps of the same approach. The first step gets two columns, the second step merges the couples of columns generated by the first step and tries to attach to every couple a third column ... it's a dynamic programming fashion of organizing the solution. The size of the setsis unknown – Gabber Jul 15 '14 at 09:23
  • It's true, I didn't get that. Anyway, are you interested in the best solution or one that is working? Meaning the smallest possible number of subsets is a requirement or the smallest number of final element. If not I would start with the bigger set (which can be measured easily) and add to this set, e.g. the more diverse from this one so as to add as much elements as possible – Eypros Jul 15 '14 at 09:28
  • My aim is the lesser number of subsets. Considering my the data I have, a working solution would be to sum all the subsets, I would find for sure a correct solution – Gabber Jul 15 '14 at 09:35
  • 1
    Did you take a look at that? http://en.wikipedia.org/wiki/Set_cover_problem – user189 Jul 15 '14 at 09:39
  • I did (just now), thanks! – Gabber Jul 15 '14 at 12:23
  • Is set A actually a multiset? If so not much you can do. Otherwise, the algorithm I gave as an answer to [this question](http://stackoverflow.com/questions/24368791/algorithm-to-detect-redundant-rules/24474558#24474558) is polynomial and sbould reduce the search space as long as set A isn't the union of all sets in B. Although, what is left afterwords becomes an instance of the [set cover problem](http://en.wikipedia.org/wiki/Set_cover_problem). – Nuclearman Jul 15 '14 at 17:32

0 Answers0