algorithm - 从节点集创建组

Question

我有一个集合列表(下面示例中的 a、b、c、d、e)。每个集合都包含该集合中的节点列表(下面的 1-6)。我想知道可能有一个通用的已知算法可以实现以下目标，我只是不知道。

sets[
 a[1,2,5,6],
 b[1,4,5],
 c[1,2,5],
 d[2,5],
 e[1,6],
]

我想生成一个新结构，一个组列表，每个组都有

• 出现在多个集合中的所有(子)节点集
• 对那些节点所属的原始集合的引用

所以上面的数据会变成(组的顺序无关紧要)。

group1{nodes[2,5],sets[a,c,e]}
group2{nodes[1,2,5],sets[a,c]}
group3{nodes[1,6],sets[a,e]}
group4{nodes[1,5],sets[a,b,c]}

我假设我可以将数据作为数组/对象结构获取并对其进行操作，然后以所需的任何格式输出结果结构。

如有以下情况将加分:

• 所有组至少有 2 个节点和 2 个集合。
• 当节点的子集包含在形成组的更大集合中时，则只有更大的集合得到一个组:在这个例子中，节点 1,2 没有自己的组，因为它们拥有的所有集合in common 已经出现在 group2 中。

(这些集合存储在 XML 中，到目前为止我还设法将其转换为 JSON，但这无关紧要。我可以理解过程(伪)代码，但也可以理解 XSLT 或 Scala 中的骨架之类的东西可以帮助获得开始了，我猜。)

Answer 1

1. 浏览集合列表。对于每个集合 S
   1. 浏览小组列表。对于每组 G
      1. 如果 S 可以是 G 的成员(即如果 G 的集合是 S 的子集)，则将 S 添加到 G。
      2. 如果 S 不能是 G 的成员，但 S 和 G 的集合的交集包含多个节点，则为该交集创建一个新组并将其添加到列表中。
   2. 给 S 自己的一组并将其添加到列表中。
   3. 合并任何具有相同集合的组。
2. 删除任何只有一个成员集的组。

例如，对于您的示例集，在读取 a 和 b 之后，组列表是

[1,2,5,6] [a][1,5] [a,b][1,4,5] [b]

读完c之后就是

[1,2,5,6] [a][1,5] [a,b,c][1,4,5] [b][1,2,5] [a,c]

如果速度有问题，可以使用稍微更高效的算法。