通用子集算法問題

Question

我有以下問題。

我有一套物品{a1, a2, a3, ... aN}。這些項目中的每一個都可以包含另一組項目{b1, b2, b3, ... bN}。所以，最終的結果看起來是這樣的：

a1 
    b4 
    b22 
    b40 
    b11 
    b9 
a2 
    b30 
    b23 
    b9 
    b4 
    b11 
a3 
    b22 
    b4 
    b60 
    b9 

由於算法執行的結果，我想獲得，根據以下規則回落b型對象組：

1. 如果一個a型對象下的多於一個b型對象只存在於該a型對象下，它們應該被分組。
2. 如果在多於一個a型對象中使用多個b型對象，也應該對它們進行分組。

例子：

b4, b9 
b30, b23 

b40, b60, b11 and b22 shouldn't be grouped because there are no pairs for them. 

我會寫這個算法在C＃中的實現，所以這將是很好的避免不其存在的數據結構，如二進制樹，鏈表等等，但這不是要求;所有這些都可以實施。

澄清：集合可以根據需要包含儘可能多的對象，但不能多於1個。規則是所有在同一個a類型中的b類型的唯一對象應該被分組（大於1），並且如果多於一個b類型的對象屬於多於1個a類型的對象，它們應該被分組。這些團體應該儘可能大。

活生生的例子：網站頁面A型並在這些網頁中使用的CSS文件b型。爲了加快頁面的加載速度，你希望有儘可能少的請求到達服務器，所以你結合了CSS文件，但是你不想合併僅在幾頁上使用的文件，因爲它們將被緩存，並且不必再次重新下載它們。

Answer 1

首先，創建一個映射，將每個b型項目與包含該b型項目的a型項目的集合相關聯。

在你的榜樣，你會得到：

B4：{A1，A2，A3}

B9：{A1，A2，A3}

B11：{A1，A2}

B22：{A1，A3}

B23：{A2}

B30：{A2}

B40：{A1}

B60：{A3}

要創建該圖，在一個類型的對象掃描所有的B型的對象，並且如果b型對象沒有關聯，在地圖上爲它創建一個條目;但是將a型對象添加到與b型對象關聯的集合中。

然後，比較每對可能的集合（O（n2））。如果兩個b型對象具有相同的一組a型對象，則合併兩個b型對象。

它被實現爲映射上的一對嵌套循環（I = 1到N-1，J = N + 1到N）。

要比較兩組，請使用set庫及其比較運算符。

如果a型對象可能由小整數表示，那麼可以將該集表示爲位數組，它比較緊湊且快速。