快捷方式，如果子集包含子集

給定的名單

我有一組K個元素的

這組的每個子集是由STD的實例表示::位集合（位我是真的=還有就是元素i的子集）

我有一個輸入的子集I，和子集S1的列表...錫

我想從S1返回的項目.. .Sn，使得Si包含在I中（即，每當Si有一點成立時，它必須是真實的，因爲我們ll）

顯然這可以在K * n中完成，通過獨立地對每個S子集執行相同的檢查。

但是，有沒有一種通用的方法可以做得更好？我很確定這是可能的，因爲在我的情況下，子集列表S1 ... Sn始終是相同的，並且可以進行預處理。我相信這將會是可能的子集存儲在一個特定的數據結構（樹？線索？），這樣我可以放棄很多相同一氣呵成，等

example : 
K = 5 

I = [1,1,0,1,0] 

S1 = [1,0,0,0,0] 
S2 = [1,1,0,1,0] 
S3 = [1,1,1,0,0] 

the ouput should return S1,S2 (not S3!)

我有一個不變設置S1,S2,...,Sn，並在相同的集合上運行I的不同查詢。

編輯：如果S1包括在S2 比如：我說的是什麼樣的例如檢查S1包括在I：如果沒有，那麼S2可以不包括在我（沒有檢查需要）如果S3是S1和S2的結合：如果S1和S2包含在I中，那麼S3

來源

2015-09-09 lezebulon

不確定我關注'我想返回S1 ... Sn中的項目，使得Si包含在I.中，如果它與我有一點共同點，你想返回Si嗎？形式上，你在尋找'{S_i | S_i [intersection] I！= {}}？也許增加一個例子會澄清你到底是什麼。 – amit

我添加了一個例子 – lezebulon

明白了，還有，關於集合S1，..，Sn'的任何知識，任何排序順序？否則，你的'O（K * n）'基本上是線性時間，我不認爲有可能在沒有實際讀取所有輸入的情況下完成它，除非有一些你可以使用的命令。（如果你有常數集S1，...，Sn和'I'總是等價的話，你可以改進它） – amit

構建一個二叉樹T所有S1...Sn其中每個等級k有兩個兒子節點，這取決於是否S有0或k位置1。樹的葉子都是你的S1...Sn。

給定的輸入集I讓我們Ik（在位置k元素）：如果你Ik==0在K水平選擇對應於0。如果Ik==1您選擇在K水平T兩個子樹的T子樹。在T上以這種方式繼續下去，直到你到達所有的葉子。

~~在最壞的情況下，您可以對給定的I進行O(n+k)操作。~~

由於S1...Sn不會改變，構建樹T是一次性操作。

編輯：我對我的回答一直很倉促。樹T有多於n葉子，它有2^k=m樹葉。但是我們可以刪除不在S1...Sn中的葉子和死亡子樹。這將成本分析帶到O(2^k)，但實際上我們將有更少的節點。現在分析變得更加困難，如果它的價值取決於m和n之間的比率;

我提出不同的分析方法：認爲在等級k我們放棄所有的子集S與在固定時間k水平無效位，但我們必須在每級O(n)子樹這樣做。由於該操作重複k次，所以最大費用將是O(kn)，但平均實際上更少。

來源

2015-09-09 10:58:01

不確定複雜性分析。如果你「選擇兩個子樹」，你需要繼續選擇他們的孩子，假設'Ik = [1,1,1 ..，1]'。在這種情況下，在根級別，您需要檢查1個節點。在下一級，2個節點，下一級4個節點（依此類推）。這基本上總結了檢查從根到每片葉子的完整路徑。有'n'葉子，路徑長度爲'k' - 因此最壞情況下的複雜度仍然是'O（nK）'。現在，我並沒有聲稱這是一個壞主意，或者它可以比'O（nk）'做得更好，只是糾正了這種方法的最壞情況。 – amit

你甚至可以使用'vector'。但實際上，你只是將每個可能的結果存儲在內存中。 – Jarod42

具有N葉和k級（k = log（n））的二叉樹總共有2n-1個節點（包括樹葉）。每個節點最多選擇一次。 –

您可以使用inverted index方法。雖然它不能改善最差情況下的性能，但它可能會加快平均情況下的速度，特別是對於相對密集的查詢向量。

對於每個j = 1,2，...，k創建一個排序列表，其中每個子集在該列表中，如果j在S_i中。這隻在預處理中創建一次。

在您的例子，它會是這樣的：

0 -> [S1,S2,S3] 
1 -> [S2,S3] 
2 -> [S3] 
3 -> [S2] 
4 -> []

現在，給出一個查詢I發現，包括「下降」的I位一個所有集合。這與信息檢索中的OR查詢相同。這個查詢的答案是不在結果中的子集。其餘的都是。

在您的示例中，查詢爲2 OR 4，查詢倒排索引時的結果爲：S3，因此結果爲S1，S2。

這基本上就是搜索引擎做的，它是非常有效的，如果查詢包括極少數條款相比，可能性的數量。

來源

2015-09-09 09:30:27 amit

好吧，如果我沒有弄錯，時間會與N *成比例（我的0數），對不對？所以這確實會在很多情況下加速 – lezebulon

它實際上更像'（NR）*（I中的0的數量）+ R'，其中'R'是結果集的大小（這仍然不嚴密，因爲它是假設所有NR集都在每個列表中）。就像我說的那樣，沒有改善最壞的情況 - 但它會讓很多人加速。 – amit

回答我的問題與部分答案：

...SN我們建立子集的樹，使得根節點是空的子集（全0位集），並且使得每個孩子包含其父子集
對於算法，從根開始：
- 每個孩子：
  - 如果在這個節點的子集包含在我，添加此子集，並以該節點爲根
  - 否則再次調用算法，進入下一個孩子（子樹爲這個孩子永遠不會被處理）

現在的問題是，如何從1）最佳地構建樹？也就是說，它具有最大深度和最小「寬度」。例如，在我的示例中，「壞」樹將是S1，S2和S3是根節點的子節點。一棵「好」的樹會是根節點只有S1的孩子，而S1的樹有S2和S3孩子。我不知道如何建立這棵樹然而

來源

2015-09-09 10:50:40 lezebulon

快捷方式，如果子集包含子集

回答

相關問題