重複するセットを見つける

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

見つける必要はありません すべて 組み合わせ、できるだけ多くのユニークな数字を見つけるのに十分です。これは、より効率的なアルゴリズムを作成して活用することが可能です。

私が言及するのを忘れていた重要なポイント：事前に、私は何のセットがあるかを事前に知りません、代わりに私はそれらを1つずつ追加し、必要なすべての数を見つけたかどうかを毎回決定する必要があります。したがって、アルゴリズムは、新しいセットが追加されると段階的に実行できるものでなければなりません。

NB。 C＃のソリューションはボーナスマークを取得します;）

Answer 1

貪欲なセットカバーを使用することのある種の修正によって、いくつかの素晴らしいソリューションを得ることができると思います（http://en.wikipedia.org/wiki/set_cover_problem）アルゴリズム。

pseudocode] so：

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ループをOMMITすることができます
• これにより、各セットのソリューションが1つしかありません（これを修正するには、問題を直接セットカバーの問題に変更し、貪欲なセットカバーを使用できます）。たとえば、配列[1,3,4]の場合、見つける必要があります。サイズ= 2：[1,3]、[1,4]、[3,4]を持つITのすべてのサブセットのSCV問題の解です。問題がはるかに複雑になります
• あなたが考慮する別の方法は進化アルゴリズムです（ここでの表現は非常に単純で、指定された数をビットとして扱い、フィットネス関数は1に近づくべきです）が、これはまだ計算後に新しいセットを追加する問題を解決しません（おそらくあなたが最後の問題から最高の人口を持つ、次に新しいセットを追加した後、染色体に新しい場所を追加するだけです）