Java Program to Solve Set Cover Problem

This is a java program to solve set cover problem. The set covering problem (SCP) is a classical question in combinatorics, computer science and complexity theory.Given a set of elements \{1,2,…,m\} (called the universe) and a set S of n sets whose union equals the universe, the set cover problem is to identify the smallest subset of S whose union equals the universe. For example, consider the universe U = {1, 2, 3, 4, 5} and the set of sets S = {{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}}. Clearly the union of S is U. However, we can cover all of the elements with the following, smaller number of sets: {{1, 2, 3}, {4, 5}}.

Here is the source code of the Java Program to Solve Set Cover Problem assuming at max 2 Elements in a Subset. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

```
 
```
```
package com.sanfoundry.setandstring;
```
```
 
```
```
import java.util.ArrayList;
```
```
import java.util.Arrays;
```
```
import java.util.Collections;
```
```
import java.util.Comparator;
```
```
import java.util.LinkedHashSet;
```
```
import java.util.List;
```
```
import java.util.Set;
```
```
 
```
```
public class SetCoverMax2Elem
```
```
{
```
```
    interface Filter<T>
```
```
    {
```
```
        boolean matches(T t);
```
```
    }
```
```
 
```

    private static <T> Set<T> shortestCombination(Filter<Set<T>> filter,

```
            List<T> listOfSets)
```
```
    {
```

        final int size = listOfSets.size();

```
        if (size > 20)
```

            throw new IllegalArgumentException("Too many combinations");

```
        int combinations = 1 << size;
```

        List<Set<T>> possibleSolutions = new ArrayList<Set<T>>();

        for (int l = 0; l < combinations; l++)

```
        {
```

            Set<T> combination = new LinkedHashSet<T>();

            for (int j = 0; j < size; j++)

```
            {
```

                if (((l >> j) & 1) != 0)

                    combination.add(listOfSets.get(j));

```
            }
```

            possibleSolutions.add(combination);

```
        }
```

        // the possible solutions in order of size.

        Collections.sort(possibleSolutions, new Comparator<Set<T>>()

```
        {
```

            public int compare(Set<T> o1, Set<T> o2)

```
            {
```

                return o1.size() - o2.size();

```
            }
```
```
        });
```

        for (Set<T> possibleSolution : possibleSolutions)

```
        {
```

            if (filter.matches(possibleSolution))

                return possibleSolution;

```
        }
```
```
        return null;
```
```
    }
```
```
 
```

    public static void main(String[] args)

```
    {
```

        Integer[][] arrayOfSets = { { 1, 2 }, { 3, 8 }, { 9, 10 }, { 1, 10 },

                { 2, 3 }, { 4, 5 }, { 5, 7 }, { 5, 6 }, { 4, 7 }, { 6, 7 },

```
                { 8, 9 }, };
```

        Integer[] solution = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

        List<Set<Integer>> listOfSets = new ArrayList<Set<Integer>>();

        for (Integer[] array : arrayOfSets)

            listOfSets.add(new LinkedHashSet<Integer>(Arrays.asList(array)));

        final Set<Integer> solutionSet = new LinkedHashSet<Integer>(

                Arrays.asList(solution));

        Filter<Set<Set<Integer>>> filter = new Filter<Set<Set<Integer>>>()

```
        {
```

            public boolean matches(Set<Set<Integer>> integers)

```
            {
```

                Set<Integer> union = new LinkedHashSet<Integer>();

                for (Set<Integer> ints : integers)

```
                    union.addAll(ints);
```

                return union.equals(solutionSet);

```
            }
```
```
        };
```

        Set<Set<Integer>> firstSolution = shortestCombination(filter,

```
                listOfSets);
```

        System.out.println("The shortest combination was " + firstSolution);

```
    }
```
```
}
```

Output:

$ javac SetCoverMax2Elem.java
$ java SetCoverMax2Elem
 
The shortest combination was [[1, 2], [3, 8], [9, 10], [5, 6], [4, 7]]

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

« Prev - Java Program to Implement String Search Algorithm for Short Text Sizes

» Next - Java Program to Find Majority Element in a Sorted Array

Related Posts:

Recommended Articles: