用於確定哪些集合是較大集合的子集的高效搜索算法

考慮集合集合A1,A2，...，An。我想確定找到哪些這些集合是不同集合的子集的最有效算法B。用於確定哪些集合是較大集合的子集的高效搜索算法

例如，讓算法的輸入是：

A1 = [1 2] 
A2 = [2 3 4] 
A3 = [1 3] 
B = [1 2 3]

該算法應該返回：

output = [1 3]

因爲A1和A3是B但A2子集是沒有的。

來源

2016-11-19 jonem

如果你想要任何聰明的優化，你必須把這個操作放在上下文中。就其本身而言，你可以做的事情不多。從'B'排序或建立一個哈希表，然後運行相應的標準遏制測試是你所能做的。 – user2357112

@ user2357112嗨，謝謝你的評論。爲了給出更多的上下文：集合B包含從集合1到大約1000或10000的整數集合（沒有重複集合）。有許多集合A，數量爲1000，其中只包含1到3個整數（同樣沒有重複）來自同一組（1到1000或10000）。 – jonem

簡單的O（N）答案：從兩個列表開始排序。選擇較短的列表，併爲每個條目檢查它是否存在於另一側。您不需要對另一個列表進行奇怪的搜索，只需保留一個指針並遞增，直到找到或傳遞我們的目標編號。

另一方面，您仍然可以通過簡化計算機的每個步驟來加速「O（N）」操作。例如，如果您只需要計算共有多少個數字，則可以使用bitmask

相當快地計算如果您將許多列表與一個特殊列表進行比較，並且大多數數字不會相同，你可以創建一個Bloom Filter。這可以很快告訴你「編號X不在Y組」。它不能告訴你該號碼是否存在 - 你必須手動仔細檢查。如果您認爲MOST數字未命中，那麼這是一個速度勝利，只有少數會成爲命中。

來源

2016-11-19 06:36:29 BraveNewCurrency

感謝您的回答！我有幾個問題：1）對於位掩碼方法，如果我知道'A1 = [1 2]'和'B = [1 2 3]'，並且操作告訴我有兩個共同的元素，I知道'A1'必須在'B'中，因爲'A1'中只有兩個元素。同樣，說'B = [1 3]'，那麼只有一個共同的元素，'A1'不是'B'的子集。因此，總之，我可以通過簡單比較共同的數字來檢查子集嗎？ I.E.當且僅當'A1'不是'B'的子集時，共同元素的數量（在'A1'和'B'之間）小於'A1'中元素的數量？ – jonem

2）爲了將引用的文本概括爲「set X不在集合Y中」，是否必須測試X中的所有數字以確定X是否是Y的子集？我不確定這將如何直接比較兩個列表來幫助提高效率。 – jonem

只有你足夠了解你的數據，才能知道哪些捷徑是有價值的。例如，你可以問「A中最大的元素是否小於B中的最小元素」？如果你的數據重疊很多，這將是一種浪費，因爲這很少會跳過工作。但是如果你注意到你的數據很少重疊，那麼這可能是一場勝利。 – BraveNewCurrency

用於確定哪些集合是較大集合的子集的高效搜索算法

回答

相關問題