通过共同的元素分组名单 [英] Grouping lists by common elements

问题描述

我在寻找一个聪明/快C ++算法，这样可以让我做对象的若干名单进行分组时，里面含有共同的对象。比方说，我有N个列表，其中一个元素E关联每片含1..M对象（O）：

I'm looking for a clever/fast C++ algorithm, which would allow me to do grouping of several lists of objects when they contain common objects inside. Let's say I have N lists, each containing 1..M objects (O) associated with one element E:

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

我要重新安排他们到以下内容：

I wish to rearrange them into the following:

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

结果与所有相关联的元素组合在一起的所有常见的对象。没有对象是在列表之间到底共享。

The result has all common objects grouped together with all associated elements. No object is shared in the end between lists.

推荐答案

对于每一个对象，计算出该元素包含它。

For each object, calculate which elements contain it.

即

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

这些列表诱导的曲线图：有每一个元件顶点，和两个顶点相连接，如果相应元素显示在同一列表

These lists induce a graph: there's a vertex per element, and two vertices are connected if the corresponding elements show up in the same list.

在我看来，要计算什么是连接组件图的。

It seems to me that what you want to calculate are the connected components of the graph.

这篇关于通过共同的元素分组名单的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！