# 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.

1. ` `
2. `package com.sanfoundry.setandstring;`
3. ` `
4. `import java.util.ArrayList;`
5. `import java.util.Arrays;`
6. `import java.util.Collections;`
7. `import java.util.Comparator;`
8. `import java.util.LinkedHashSet;`
9. `import java.util.List;`
10. `import java.util.Set;`
11. ` `
12. `public class SetCoverMax2Elem`
13. `{`
14. `    interface Filter<T>`
15. `    {`
16. `        boolean matches(T t);`
17. `    }`
18. ` `
19. `    private static <T> Set<T> shortestCombination(Filter<Set<T>> filter,`
20. `            List<T> listOfSets)`
21. `    {`
22. `        final int size = listOfSets.size();`
23. `        if (size > 20)`
24. `            throw new IllegalArgumentException("Too many combinations");`
25. `        int combinations = 1 << size;`
26. `        List<Set<T>> possibleSolutions = new ArrayList<Set<T>>();`
27. `        for (int l = 0; l < combinations; l++)`
28. `        {`
29. `            Set<T> combination = new LinkedHashSet<T>();`
30. `            for (int j = 0; j < size; j++)`
31. `            {`
32. `                if (((l >> j) & 1) != 0)`
33. `                    combination.add(listOfSets.get(j));`
34. `            }`
35. `            possibleSolutions.add(combination);`
36. `        }`
37. `        // the possible solutions in order of size.`
38. `        Collections.sort(possibleSolutions, new Comparator<Set<T>>()`
39. `        {`
40. `            public int compare(Set<T> o1, Set<T> o2)`
41. `            {`
42. `                return o1.size() - o2.size();`
43. `            }`
44. `        });`
45. `        for (Set<T> possibleSolution : possibleSolutions)`
46. `        {`
47. `            if (filter.matches(possibleSolution))`
48. `                return possibleSolution;`
49. `        }`
50. `        return null;`
51. `    }`
52. ` `
53. `    public static void main(String[] args)`
54. `    {`
55. `        Integer[][] arrayOfSets = { { 1, 2 }, { 3, 8 }, { 9, 10 }, { 1, 10 },`
56. `                { 2, 3 }, { 4, 5 }, { 5, 7 }, { 5, 6 }, { 4, 7 }, { 6, 7 },`
57. `                { 8, 9 }, };`
58. `        Integer[] solution = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };`
59. `        List<Set<Integer>> listOfSets = new ArrayList<Set<Integer>>();`
60. `        for (Integer[] array : arrayOfSets)`
61. `            listOfSets.add(new LinkedHashSet<Integer>(Arrays.asList(array)));`
62. `        final Set<Integer> solutionSet = new LinkedHashSet<Integer>(`
63. `                Arrays.asList(solution));`
64. `        Filter<Set<Set<Integer>>> filter = new Filter<Set<Set<Integer>>>()`
65. `        {`
66. `            public boolean matches(Set<Set<Integer>> integers)`
67. `            {`
68. `                Set<Integer> union = new LinkedHashSet<Integer>();`
69. `                for (Set<Integer> ints : integers)`
70. `                    union.addAll(ints);`
71. `                return union.equals(solutionSet);`
72. `            }`
73. `        };`
74. `        Set<Set<Integer>> firstSolution = shortestCombination(filter,`
75. `                listOfSets);`
76. `        System.out.println("The shortest combination was " + firstSolution);`
77. `    }`
78. `}`

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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now! 