按常用元素分組列表

我正在尋找一種聰明/快速的C++算法，當它們包含公共對象時，可以對幾個對象列表進行分組。比方說，我有N個列表，其中一個元素E相關的每片含1..M對象（O）：按常用元素分組列表

[O1, O2]  -> E1 
[O3]   -> E2 
[O1, O4, O5] -> E3 
[O2, O5]  -> E4 
[O3, O6]  -> E5

我希望他們重新安排到以下幾點：

[O1, O2, O4, O5] -> [E1, E3, E4] 
[O3, O6]   -> [E2, E5]

結果又全部與所有相關元素一起分組的共同對象。列表之間最後沒有共享對象。

來源

2013-03-19 krojew

那麼，你有什麼嘗試？你如何閱讀你的輸入數據？ – 2013-03-19 15:29:41

你有沒有考慮['multimap']（http://en.cppreference.com/w/cpp/container/multimap）？參見[何時使用std :: multimap意義]（http://stackoverflow.com/questions/8342445/when-does-using-a-stdmultimap-make-sense） – 2013-03-19 15:34:19

對於每個對象，計算哪些元素包含它。

即

01 -> [E1, E3] 
02 -> [E4] 
03 -> [E2, E5] 
04 -> [E3] 
05 -> [E3, E4] 
06 -> [E5]

這些列表誘導的曲線圖：有一個頂點每個元素，並且如果相應的元件以相同的列表中顯示的兩個頂點相連接。

enter image description here

在我看來，要計算什麼是圖的connected components。

來源

2013-03-19 15:31:08 abeln

如果對象O被用作節點會怎麼樣？像boost :: graph :: connected_components這樣的助手可以在線性時間內生成對象組，然後可以使用簡單的O> E multimap爲每個對象組生成元素組。還沒有機會測試它，所以我不知道這是否是一個正確的方法。 – krojew 2013-03-20 08:13:56

這也可以。 – abeln 2013-03-20 14:45:44

按常用元素分組列表

回答

相關問題