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
