按常用元素分组列表

我正在寻找一种聪明/快速的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

按常用元素分组列表

回答

相关问题