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

一尘不染

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

algorithm

我正在尝试对对象进行分类。每个对象都由称为的唯一标识符属性标识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属于同一类别，带有id9和的对象id2属于同一类别，带有的对象id1,id2,id3,id9应该属于同一类别。所以我应该有这样的集合set(id1,id2,id3,id9)
有人可以提供算法吗？谢谢

阅读 256

2020-07-28

共1个答案

一尘不染

听起来您正在寻找不连续的数据结构。

给定您的ID集，您的类别会将它们分成不相交的子集。不相交的数据结构通过选择一个代表ID来表示每个类别，该ID将由对其任何成员的查询返回。（被隔离的ID各自构成一个类别，然后返回自己）

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

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

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

如果要在线访问每个类别中ID的完整列表，则应维护一个附加到每个类别根目录的累积列表，并在每次合并中将它们串联起来。通常，以这种方式维护有关类别的大量统计信息会很方便。

2020-07-28