合并至少有一个共同元素的集合

Question

合并至少有一个共同元素的集合

3

可能重复：

Python：基于交集的简单列表合并

我正在尝试对对象进行分类。每个对象都由一个名为id的唯一标识符属性来标识。因此，我的分类逻辑如下。首先，我准备了一个对象列表，然后分类函数每次取2个对象，并返回一个包含它们的id的frozenset。因此，如果object1和object5属于同一类别，则返回frozenset(id1,id5)。现在，我将这些frozensets添加到一个set中，最终我会得到一个类似于这样的set：

matched_set=(
             frozenset(id1,id2),
             frozenset(id9,id3),
             frozenset(id9,id2),
             frozenset(id24,id22),
             frozenset(id1,id23),
             frozenset(id25,id24),
             frozenset(id30,id24)
            )

现在，因为具有id1和id2的对象属于同一类别，具有id9和id3的对象属于同一类别，具有id9和id2的对象属于同一类别，具有id1，id2，id3，id9的对象应该属于同一类别。所以我应该有一个像这样的集合set(id1,id2,id3,id9)。请问是否可以提供一个算法来实现这个功能？谢谢

- lovesh

2

链接的问题包含了几个可行的解决方案。 - undefined

@DSM 非常感谢你指引我去那个地方。 - undefined

要查看多种语言的答案，请访问http://rosettacode.org/wiki/Set_consoldation。 - undefined

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- comingstorm · Accepted Answer

看起来你正在寻找一个不相交集合数据结构。

给定你的id集合，你的类别将它们分成不相交的子集。不相交集合数据结构通过选择一个代表id来表示每个类别，该代表id将由任何其成员的查询返回。（孤立的id形成一个类别，并返回它们自己）

对不相交集合数据结构的更新将组合任意两个id的类别，以便将来的查询为两个子集的成员返回相同的代表。（如果两个id已经是同一类别的成员，则更新实际上是无操作的）

通常的方法是将每个类别表示为反向树：每个id都有一个parent链接，但没有子链接。 “代表元素”是树的根，可以通过跟随父链接轻松查询。更新需要找到两个id的树的根，然后（如果它们不同）通过使一个根成为另一个根的父来合并树。

通过添加一些简单的优化（将查询路径“折叠”为直接指向根，更新始终选择最深树的根作为合并父节点），该算法变得非常高效，以“几乎O（1）”的摊销时间运行。

如果您想在线访问每个类别中完整ID列表，应该维护附加到每个类别根的累积列表，并在每次合并时连接它们。通常，通过这种方式维护任意数量的有关类别的统计信息可能很方便。