用於比較包含集合的列表的部分的高效算法

Question

在我的應用程序中，我需要比較集合列表的部分以查看它們是否包含相同的元素。我基本上有以下結構：

List 1 Index Set 
1    (1,5) 
2    (3,7) 
3    () 
4    (1,9,15) 

我有一些約20列出每個列表中超過千組。列表中的集合可以是空的，也可以包含多達數百個元素。

我需要爲我的列表的不同間隔創建這些集合的聯合。 因此，例如，我想用follwoing列表進行比較前者名單的時間間隔：

List 2 Index Set 
1    (3,6,9) 
2    (2) 
3    (20) 

間隔列表1 2至4間隔列表2從1至2相比應該給（3,9）

目前我使用一個簡單的運行通過蠻力方法都列出比較每個集。有沒有更有效的解決方案？

在此先感謝

Answer 1

一種方法可能是爲每個這樣的列表，輔助列表，包含在該出現在套到現在的元素各項指標柱狀圖。

在您的例子：

List Index  histogram 
1    [1=1, 5=1] 
2    [1=1, 3=1, 5=1, 7=1] 
3    [1=1, 3=1, 5=1, 7=1] 
4    [1=2, 3=1, 5=1, 7=1, 9=1, 15=1] 

現在，給出了兩個指標，i,j - 你可以創建聯盟集索引集的我，我+ 1，...，通過採取兩個直方圖記者： hist1=list[i-1], hist2=list[j]，並返回所有元素x，使得hist1.get(x) < hist2.get(x)，並獲得聯合集而不實際迭代列表。

例如，在上面的列表中，如果你想找到的指數2,3,4工會名單：

hist1=list[1] = [1=1, 5=1] 
hist2=list[4] = [1=2, 3=1, 5=1, 7=1, 9=1, 15=1] 
hist2-hist1 = [1=2-1, 3=1-0, 5=1-1, 7=1-0, 9=1-0, 15=1-0] = 
      = [1=1, 3=1, 5=0, 7=1, 9=1, 15=1] 
union_set = {1,3,7,9,15} 

這種方法是非常有用的，當集比列表，小得多這似乎是你的情況。