優化組合和組合

Question

我有一堆組A1，A2，A3，... AN。每組包含N個元素（可以說1000個最大值），其值爲0到2000。

A1{1,2,3,4} 
A2{2,4,3,5} 
A3(1,2,5,6) 

現在對於k的大小，例如， 3，A1的組合將是C1（1,2,3），C2（1,2,4），C3（2,3,4）對於A1到AN，我需要弄清楚A1中的所有組合是否存在某處在A2到AN的組合中。

即A1的組合C3將與A2中的組合匹配，並且可能與AN組合。現在我需要A1的C1和C2以及A2到AN的結果。 簡單而低效的方法是將所有集合A1到AN的k個大小的所有組合。那麼對於C1的A，其中/如果它存在於A2中，則爲AN。之後，C2，然後是C3。然後轉到下一個設置並重復。

我該如何改進這種方法，因爲一旦添加了新套件，它需要頻繁且昂貴的計算？

我發現的另一個解決方案將在O（N^2 + N）中運行而不進行優化，基本上涉及到A1和A2的交點... AN，計算這些交點的組合，然後查看多少次每個組合都會在生成的結果中出現。

Answer 1

你可以嘗試哈希你的組合。 您可以在這裏使用兩種方法，一種優化空間，另一種優化時間。 爲了優化時間，你的散列函數將爲每個組合創建一個唯一的鍵，並且只要你在已經佔據的地方被擊中，你就會知道你不是第一次遇到這個組合。 對於空間優化方法是類似的，但關鍵不會是唯一的。您必須管理相應組合的列表，然後點擊遍歷它以查看它是否包含您當前正在檢查的組合。您的鑰匙的唯一性等級將定義您的表格的大小，因此您必須花費時間驗證命中。