我有一个如下数据集-List((X,Set(" 1", " 7")), (Z,Set(" 5")), (D,Set(" 2")), (E,Set(" 8")), ("F ",Set(" 5", " 9", " 108")), (G,Set(" 2", " 11")), (A,Set(" 7", " 5")), (M,Set(108)))
这里X与A相关,因为7在它们之间很常见
Z与A相关,因为5在它们之间很常见
F与A有关,因为5在它们之间很常见
M与F有关,因为108在它们之间很常见
因此,X、Z、A、F和M是相关的
D和G是相关的,因为2是它们之间的共同点
E与任何人都没有血缘关系
因此,输出将是((X,Z,A,F,M),(D,G),(E))
在这里,秩序并不重要。
我在这里使用了Scala,但Scala/Python或伪代码的解决方案对我来说是有效的。
4条答案
按热度按时间enxuqcxy1#
构建一个无向图,其中每个标签都连接到相应集合中的每个数字(即
(A, { 1, 2 })
将给出两条边:A <-> 1
和A <-> 2
)计算连通分量(例如,使用深度优先搜索)。
仅从连接的组件中过滤出标签。
可按如下方式使用:
产生:
所有步长都是
O(n)
(随输入大小线性调整)。这个答案是自成一体的,但在这里使用某种图形库显然是有利的。
pwuypxnk2#
最终使用的是一种更简单的解决方案,如下所示:
以下列方式获取输出:
对更多的几个数据集进行了测试,似乎运行良好。
hgtggwj03#
//我将一些值放在引号中,这样我们就有了一致的字符串输入
//通过将集合中的字符串数据转换为Int来清理集合
//将集合分解为简单Map列表。X->1,X->7。
将它们按新密钥组合在一起
打印输出
t0ybt7op4#
例如:
E.g
例如:
下面是实现这一点的C++代码
它会产生正确的结果