Нахождение перекрывающихся множеств

Question

Я пишу систему цифрового фонтана на C#. Часть этой системы создает мне наборы целых чисел, мне нужно найти комбинации наборов, которые создают, могут оставить мне набор только из одного элемента. Какой самый быстрый способ сделать это?

Set A: 1,2,3,4,5,6
Set B: 1,2,3,4,6
Set C: 1,2,3
Set D: 5,6

Solutions:
A - B => 5
A - (C + D) => 4

Мне не нужно находить все комбинации, достаточно просто найти мне как можно больше уникальных чисел. Это может быть возможно использовать для создания более эффективного алгоритма.

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

В северном направлении Решения в C# получают бонусные оценки;)

Answer 1

Я думаю, что некоторые хорошие решения могут быть получены с помощью некоторой модификации использования алгоритма жадного набора обложек ( http://en.wikipedia.org/wiki/Set_cover_problem).

[псевдокод] так:

1. sort sets by size descending
2.
foreach set in sets do:
  uncovered = set.size
  while uncovered > 1
    current_set = the biggest set that covers no more than (uncovered - 1) and was not used before to cover set
    uncovered = uncovered - covered_by_set(set)
    collect current_set to some array
  end
end

редактировать:

• Вы можете пропустить цикл foreach для последнего набора
• это принесет вам не более одного решения для каждого из наборов (чтобы исправить это, вы можете изменить задачу непосредственно на проблему набора покрытий и использовать жадное покрытие набора), например, если вы массив [1,3,4], вам нужно найти решение задачи SCV для всех ее подмножеств, имеющих размер = 2: [1,3], [1,4], [3,4]. это сделает проблему намного более сложной
• Вы также можете рассмотреть алгоритмы эволюции (представление здесь будет очень простым, обрабатывать указанное число как бит, функция пригодности должна стать ближе к 1), но это по-прежнему не решает проблему добавления нового набора после вычислений (возможно, когда вы иметь лучшую популяцию из последней проблемы, то после добавления нового набора просто добавьте новое место в хромосоме)