Java Program to Solve Set Cover Problem assuming at max 2 Elements in a Subset

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.maixuanviet.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]]