Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Set Cover problem - algorithm

Posted on 2010-11-26
4
Medium Priority
?
2,042 Views
Last Modified: 2013-04-26
Hi,
Can someone please share a program in java which does the following.
if given the following sets as inputs,
a={1,2,3,8,9,10}
b={1,2,3,4,5}
c={4,5,7}
d={5,6,7}
e={6,7,8,9,10}

and U={1,2,3,4,5,6,7,8,9,10}
the program will find all the combinations of the set and find out the minimum number of sets that together has all the elements of U.
In the above example, the minimum number is 2. set b and e together covers all of U.
So basically, it is a set covering problem. In the Set Covering problem, we are given a universe U, such that |U|=n, and sets S1,……,Sk are subsets of U. A set cover is a collection C of some of the sets from S1,……,Sk whose union is the entire universe U. Additionally, we must minimize the cost of the sets.

Thanks so much in advance.
0
Comment
Question by:sarah2248
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
4 Comments
 
LVL 37

Accepted Solution

by:
TommySzalapski earned 1000 total points
ID: 34219300
Since the set cover problem is NP-Complete you can only use a greedy algorithm for small universes or the algorithm will never finish. But since your example only has 5 sets, it's not too bad.

It can be very simple if you use recursion. I'm guessing this is for an assignment, so I'm not writing the code for you, but I'll help you get started and help you if you get stuck.

Here's how I would approach it. Loop through your sets using a for loop that does this:
Take the current set S
Does S cover the universe?
If so return 1 and the name of the set.
If not, remove the sets in S from the universe and loop through the other sets (only the ones after the current one) and find the minimum that covers the remaining portion of the universe (by calling the same function this code is in). Return 1+the minimum and the set that covered plus this set.

This will give the minimum set cover in a fairly efficient time. To speed it up some, keep track of how many sets have been picked so far and the current minimum so you can just quit if the current set of sets is bigger or equal to the current minimum.

If the above is confusing, try to figure it out and let us know where you are stuck.
0
 
LVL 2

Assisted Solution

by:matstein
matstein earned 1000 total points
ID: 35932810
My solution would be as follows:

Every possible set will be 5C1 + 5C2 + 5C3 etc...

So first iterate over all sets in the 5C1 case (i.e. set A then B then C) and ask if those sets cover U if so return 1

If it doesn't generate new sets A U B, A U C etc. (in the 5C2 group) and see if those cover return 2

pseudo code is as follows:

global set A,B,C,D,E, U

checkCoverage(Set X)
{
   for each element in U is that element in X
         if yes return true
   return false
}

getminimumnumber(int group)
{
     for i = A to D do
       if checkcoverage(i,U)
         return 1
    start = B
    for i = A to D do
     {
      for j= start to E do
       {
        X = i U j
           if checkcoverage(X,U)
        }      return 2
      start = start++;

proceed similarly for the 5C3, 5C4 and 5C5 combinations
}


A more elegant way to go about it is to make all possible combinations of sets up front and then iterate through the list. Obviously this problem is NP complete as the above expert mentioned and thus the algorithm is completely useless for large numbers of sets.

0
 
LVL 101

Expert Comment

by:mlmcc
ID: 36268303
This question has been classified as abandoned and is closed as part of the Cleanup Program. See the recommendation for more details.
0

Featured Post

Moving data to the cloud? Find out if you’re ready

Before moving to the cloud, it is important to carefully define your db needs, plan for the migration & understand prod. environment. This wp explains how to define what you need from a cloud provider, plan for the migration & what putting a cloud solution into practice entails.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
In this video, Percona Solutions Engineer Barrett Chambers discusses some of the basic syntax differences between MySQL and MongoDB. To learn more check out our webinar on MongoDB administration for MySQL DBA: https://www.percona.com/resources/we…

670 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question