Set cover

Problem

There are few sets with some numbers. And you are given an array of numbers. Find combination of sets with minimum number of sets, union of which have all these numbers.

Example
input sets:
A = [1,2,3]
B = [2,5,8]
C = [1,4,5]
D = [3,5,8]

Array to find:
{3,4,8}

Answer:
C + D

Solution

Set cover is NP-hard, so, no polynomial algorithm is known to exist for it.

When you abstract away from the specifics of the problem, it is an integer program (IP). So, you can use any general purpose IP solver such as the one provided in MS-Excel. All general integer programming problems are solved using branch-and-bound method. So, you do not need one specifically for Set Covering alone. All you need to do is to formulate the set covering problem as an integer program and provide it to the solver which should take care of the rest. Folks on SO are unlikely to have a ready-made code available to share with you. Integer Programming/Linear Programming (which forms the basis for integer programming) codes are quite detailed and specialized.

Basically, look at all combinations of 1 set, then 2 sets, etc. until they form a cover.

for size in 1..|S|:
    for C in combination(S, size):
          if (union(C) == U) return C

where combination(K, n) returns all possible sets of size n whose elements come from K.

interface Filter<T> {
    boolean matches(T t);
}
public static void main(String... args) throws IOException {
    Integer[][] arrayOfSets = {
            {1, 2, 3, 8, 9, 10},
            {1, 2, 3, 4, 5},
            {4, 5, 7},
            {5, 6, 7},
            {6, 7, 8, 9, 10},
    };
    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);
}

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;
}

References

• http://www.careercup.com/question?id=19295671
• http://stackoverflow.com/questions/4287302/find-combinations-of-all-sets-set-cover