2

可能重复：
Python：基于交叉点的简单列表合并

我正在尝试对对象进行分类。每个对象都由一个称为 的唯一标识符属性标识id。所以我的分类逻辑是这样的。首先我准备一个对象列表，然后分类函数一次获取 2 个对象并返回一个frozenset包含它们的id. 因此，如果object1和object5属于同一类别，frozenset(id1,id5)则返回 a。现在我不断将这些frozensets添加到一个集合中，所以最后我有一个这样的集合

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的对象属于同一类别，具有和的对象应该属于同一类别。所以我应该有一个这样的集合 有人可以提供一个算法吗？谢谢id9id2id1,id2,id3,id9set(id1,id2,id3,id9)

4

1 回答 1

6

听起来您正在寻找不相交集的数据结构。

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

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

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

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

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

于 2012-08-21T22:01:49.590 回答