查找重疊集

Question

我正在用C＃編寫一個Digital Fountain系統。這個系統的一部分創建了我的整數集合，我需要找到創建集合的組合可以給我一套只有一個項目。什麼是最快的方法來做到這一點？

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 

我不需要找所有組合，就足以找到了我許多獨特的數字越好。這可能會被利用來創建更高效​​的算法。

重要的一點，我忘了提： 我不知道，事前，多少套也有，而不是我加入他們一個接一個，每一次必須確定，如果我發現我每次需要數。所以該算法必須是可以隨着新套件的添加而分階段運行的。

Nb。在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 

編輯：

• 可以ommit foreach循環的最後 設置
• 這會給你帶來不超過一個 解決方案每套（修復 這個你可以直接更改問題例如，如果你排列爲 [1,3,4]，你需要找到解決方案 SCV問題的所有子集 大小= 2：[1 ，3]， [1,4]，[3,4]。它將使問題 複雜得多
• 另一種方式，你可以考慮是 進化算法（表示 這裏將是非常簡單的，治療 指定數量位，健身 功能將增長接近1）， 但這仍然沒有解決的問題 計算 後增加新集（也許當你從最後一個問題最好的人口 ，然後加入 新集之後就在 染色體增加新的地方）