CS set coverage question perl

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

I am looking for any suggestions for an efficient perl solution to this problem.

The obvious solution is O(n^2).

Is there a smarter way?

Consider a collection of sets C = (S_1, S_2, ... , S_n).

Say set S_i 'covers' sets S_j, S_k, ... S_m iff S_i is a subset of S_j, is a subset of S_k, ... is a subset of S_m.

I seek the smallest subset of C that covers all members of C.

Any suggestions would be appreciated.

Comment on CS set coverage question perl

Replies are listed 'Best First'.
Re: CS set coverage question perl by jdalbec (Deacon) on Sep 26, 2004 at 17:48 UTC
In the worst case, no. We can prove this by an adversary argument. If the smallest subset is C itself, then suppose you didn't compare S_i and S_j. Your adversary replaces S_j by S_i union a singleton that is not contained in any other set. Since no S_k covers S_i and the extra element in S_j is not contained in any S_k, no S_k covers S_j. Since S_j contains a singleton not contained in any other set, it does not cover any S_k. Therefore all your comparisons will come out the same with the new and old S_j. But the new S_j should be omitted from the smallest subset since S_i covers it, so your adversary will have tricked your algorithm into producing an incorrect result.	[reply]
Re: CS set coverage question perl by exussum0 (Vicar) on Sep 26, 2004 at 14:30 UTC
What you have here is a searching problem. You have two set sets of size n and m. The running time should be O((n log n) + (m log m)) since you need to find what elements in n are in m, and which ones are m that are in n. The non theoretical answer is to use hashes and check the to see what keys exist in both.. ---- Then B.I. said, "Hov' remind yourself nobody built like you, you designed yourself"	[reply]