3

I have some vague recollections from my algorithms courses, but nothing specific comes to mind.

let S be a multiset of things we are interested in.

As input, we get T, s1, s2, ... sn, all of which are subsets of S, except that T can have duplicates .

As output we get whether it is possible to pick exactly 1 element from each si so that we end up with T. What would be really nice is if in the case of failure it told you which si's were not covered by T (although this isn't really well defined when there's non-empty intersections in the si's).

In my case, most of the time there won't be many elements which appear in more than one si's, but I have to account for the possibility. Also, an 'online' algorithm in which you provide the si's up front, and then pass in elements of T one at a time would be convenient.

This is almost like the exact hitting set problem, but I am given T, rather than trying to find a subset of T which has this property.

  • Since S is a multi-set, might T contain duplicates as well? So how are you combining the picked elements? Will you discard multiple items? I'm asking because if you don't discard duplicates, since you say that you get all multi-subsets of S, this will narrow the possible choices for T dramatically. – 5gon12eder Mar 6 '15 at 1:15
  • Well, in my case, S is the 'universe' of items, I guess it's not really a multiset. All the subsets may contain duplicates though. – Bwmat Mar 6 '15 at 1:19
  • I'm confused by the “all sub-multisets” in your question. Do you mean that once S is fixed, all the s1, …, sn are determined except for reordering? And expanding on this, if s1 = {1, 2} and s2 = {1}. If I pick 1 from s1 and 1 from s2, will the union (as defined in your domain) be {1, 1} or {1}? – 5gon12eder Mar 6 '15 at 1:26
  • Sorry for the confusing wording, I've edited the question in an attempt at clarification – Bwmat Mar 6 '15 at 1:29
  • 1
    Well, there always has to be N si's, where N is the cardinality of T. – Bwmat Mar 6 '15 at 1:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.