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 Reference Books in Java Programming, Data Structures and Algorithms.