包含超集

我正在尋找一個能夠有效檢查它是否包含我的集合超集的結構（「集合集合」）。包含超集

示例： A = {1，2} B = {2,3} C = {1,3} d = {1，2，3}

集合的集合S1 = { A，B}和另一個S2 = {d}

S1 contains A => true 
S1 contains C => false 
S2 contains A => true

對此的解決方案應該具有儘可能低的複雜性（不僅漸近）越好。

2014-10-28 JiriS

你的套件有多大？你有多少？ – 2014-10-28 12:12:18

集合通常包含少於5-10個字符串（或長整數），集合集合最多應包含約100-1000集，但在大多數情況下爲10-100集。 – JiriS 2014-10-28 13:49:24

可以設置它們自己或集合的集合是否更改（即，是否可以插入/刪除）還是全部是靜態的？ – kraskevich 2014-10-28 16:02:46

-1

使用字典在位圖中可能的不同元素和位置之間進行轉換。然後將每個集合存儲爲位圖。

考慮一組集的聯合是一起討論位圖的問題。

檢查一個集合是否是一組集合的一個子集正在檢查位圖結果和較小集合的位圖。

這些操作應該很快。如果你真的是真的雄心勃勃，你可以從http://en.wikipedia.org/wiki/General-purpose_computing_on_graphics_processing_units開始，並找出如何將計算移動到GPU。

如果你有更大的集合，並且有時會得到錯誤的答案，那麼你應該查找Bloom Filters。這可以讓你用大大縮短的位圖獲得大部分正確的答案。

2014-10-28 23:10:48 btilly

回答