find Combinaisons de tous les ensembles - set cover?

Question

Quelqu'un peut-il s'il vous plaît partager un programme en Java qui fait ce qui suit. si on leur donne les ensembles suivants comme entrées,

a={1,2,3,8,9,10} 
b={1,2,3,4,5} 
c={4,5,7} 
d={5,6,7} 
e={6,7,8,9,10} 

et

U={1,2,3,4,5,6,7,8,9,10} 

le programme trouvera toutes les combinaisons du jeu et trouver le nombre minimum de jeux qui a ensemble tous les éléments de U

Dans l'exemple ci-dessus, le nombre minimum est 2. set b et e couvrent ensemble U. Donc, fondamentalement, c'est un problème de couverture. Dans le problème Set Covering, on nous donne un univers U, tel que |U|=n, et les ensembles S1,……,Sk sont des sous-ensembles de U. Une couverture d'ensemble est une collection C de certains des ensembles de S1,……,Sk dont l'union est l'univers entier U. En outre, nous doit minimiser le coût des ensembles.

Answer 1

Qu'est-ce que vous avez besoin est de tester la taille de plus en plus de combinaisons, comme tant

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

Prints

The shortest combination was [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10]] 

Answer 2

Puisque vous voulez une solution optimale et que set cover est NP-complet, il suffit de générer toutes les combinaisons possibles par force brute. Pour une entrée de n ensembles, il y aura 2^n - 1 combinaisons possibles. Vous pouvez générer chaque combinaison à son tour comme suit:

 
let the input sets be S1, S2, ..., Sn 
let min = { S1, S2, ..., Sn } // initially assume all sets are required 
for i = 1, 2, ..., 2^n - 2 
    let X = {} 
    represent i as a binary number containing n bits 
    for each bit j that is set to 1, include set Sj in X 
    if X covers all sets and #X < #min 
    update min = X 
end 

Answer 3

Désolé pour la réponse tardive . Mais si vous êtes toujours intéressé par cela, vous pouvez obtenir des solutions approximatives pour définir la couverture en utilisant l'algorithme de Rajagopalan-Vazirani: http://portal.acm.org/citation.cfm?id=299880. Cela vous donnera des réponses qui sont au plus un facteur 2 loin de l'optimal.