найти комбинации всех комплектов - установить обложку?

Question

Может кто-нибудь поделиться программой на Java, которая делает следующее. если заданы следующие наборы в качестве входных данных,

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}

и

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

программа найдет все комбинации набора и определит минимальное количество наборов, в которых есть все элементы U.

В приведенном выше примере минимальное число равно 2. набор b и e вместе охватывает все U. Так что в основном это проблема покрытия множества. В задаче покрытия множеств нам дана юниверс U, такой, что |U|=n, а множества S1,……,Sk являются подмножествами U. Покрытие множеств представляет собой набор C некоторых из множеств из S1,……,Sk, объединение которых является целым Кроме того, мы должны минимизировать стоимость наборов.

Answer 1

То, что вам нужно, это протестировать увеличивающиеся размеры комбинаций, например:

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

Отпечатки

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

Answer 2

Извините за поздний ответ. Но если вы все еще заинтересованы в этом, вы можете получить приблизительные решения для укрытия, используя алгоритм Раджагопалана-Вазирани: http://portal.acm.org/citation.cfm?id=299880. Это даст вам ответы, которые находятся на расстоянии не более 2 от оптимального.

Answer 3

Так как вам нужно оптимальное решение, и поскольку установка покрытия является NP-полной, просто сгенерируйте все возможные комбинации с помощью грубой силы. Для ввода n наборов будет 2^n - 1 возможных комбинаций. Вы можете генерировать каждую комбинацию по очереди следующим образом:

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