问题标签 [equivalence-classes]

我正在寻找一个好的数据结构来在树的节点上构建等价类。在理想的结构中，以下操作应该是快速的（O(1)/O(n)，视情况而定）并且容易（没有神秘代码段落）：

• (A) 从根部走树；在每个节点上 --> 子转换枚举子节点的所有等效版本
• (B) 合并两个等价类
• (C) 从现有节点（子节点）和其他数据的列表中创建新节点
• (D) 找到任何结构上与node 等价的节点（即它们有相同数量的子节点，对应的子节点属于同一个等价类，并且它们的“其他数据”相等），以便可以放入新的（或新修改的）节点在正确的等价类中（通过合并）

到目前为止，我已经考虑过（其中一些可以组合使用）：

• 冻糕，其中子代是对节点集合的引用，而不是对节点的引用。(A) 速度快，(B) 需要遍历树并更新节点以指向合并的集合，(C) 需要找到包含新节点的每个子节点的集合，(D) 需要遍历树
• 通过节点的特征维护节点的哈希。这使得 (D) 更快但 (B) 更慢（因为当等价类被合并时哈希必须被更新）
• 将节点串在一起形成一个循环链表。(A) 很快，(B) 会很快，但是事实上，将循环列表的一部分与自身“合并”实际上会拆分列表 (C) 会很快，(D) 需要遍历树
• 与上面类似，但在每个节点中都有一个额外的“向上”指针，可用于查找循环列表的规范成员。

我错过了一个甜蜜的选择吗？

我有一个将一个数据库转换为另一个数据库的项目。原始数据库列之一定义行的类别。此列应映射到新数据库中的新类别。

例如，假设原始类别是：parrot, spam, cheese_shop, Cleese, Gilliam, Palin

现在这对我来说有点冗长，我希望将这些行分类为sketch, actor- 也就是说，将所有草图和所有演员定义为两个等价类。

这很尴尬 - 我更喜欢这样的东西：

但这当然会将整个元组设置为键：

任何想法如何在 Python 中创建一个优雅的多对一字典？

假设你有很多元素，你需要跟踪它们之间的等价关系。如果元素 A 等价于元素 B，则它等价于 B 等价的所有其他元素。

我正在寻找一种有效的数据结构来编码这些信息。应该可以通过与现有元素的等价来动态添加新元素，并且从该信息中应该可以有效地计算新元素等价的所有元素。

例如，考虑以下元素 [0,1,2,3,4] 的等价集：

其中等号表示等价。现在我们添加一个新元素5

并强制等价5=3，数据结构变为

由此，人们应该能够有效地迭代任何元素的等价集。对于 5，这个集合是 [3,4,5]。

Boost 已经提供了一个方便的数据结构disjoint_sets，它似乎可以满足我的大部分要求。考虑这个说明如何实现上述示例的简单程序：

如上所示，可以有效地添加元素，并动态扩展不相交的集合。如何有效地迭代单个不相交集合的元素，而不必迭代所有元素？

我使用 VS 2008、.net 3.5、C# 项目。我需要在功能上像 Microsoft.VisualBasic.FileIO.FileSystem.DeleteDirectory 一样。

任何人都说在 C# 中引用 Microsoft.VisualBasic 通常是不可取的。在 C# 代码中与 VB 的任何关联都让我觉得不受欢迎。

使用 FileSystem 类，这是一个完美的解决方案，但我不喜欢引用 Microsoft.VisualBasic 库。我会避免的那个。

其他示例： 如何将文件放入回收站而不是删除？

Java有一个Comparator<T>用于提供类本身外部对象的比较，以允许进行有序比较的多个/替代方法。

但是进行无序比较的唯一标准方法是equals() 在类中覆盖。

当我想在类外部提供多个/交替的无序比较时，我应该怎么做？（明显的用例是根据特定属性将集合划分为等价类。）

假设最终用途是用于无序检查（例如，不用于排序或索引），是否可以实现Comparator<T>只检查是否相等，如果两个对象相等则返回 0，当两个对象不相等时返回值！= 0？（注意：我不跳上这个解决方案的唯一原因是，从技术上讲，它可以Comparator通过不提供满足传递性和对称性的关系来打破合同。）

似乎应该有一个EqualsComparator<T>标准类或其他东西。

（番石榴能处理这样的事情吗？）

考虑有一些整数列表：

问题是合并具有至少一个共同元素的列表。因此，仅给定部分的结果将如下所示：

对大数据（元素只是数字）执行此操作的最有效方法是什么？tree结构需要考虑吗 ？我现在通过将列表转换sets为交叉点并迭代交叉点来完成这项工作，但这很慢！此外，我有一种如此初级的感觉！此外，该实现缺少一些东西（未知），因为某些列表有时仍未合并！话虽如此，如果您提出自我实现，请慷慨并提供一个简单的示例代码 [显然Python是我最喜欢的 :)] 或伪代码。
更新 1： 这是我使用的代码：

功能是（越野车！！）：

结果是：

更新 2： 根据我的经验，下面Niklas Baumstark给出的代码对于简单的情况来说要快一些。尚未测试“Hooked”给出的方法，因为它是完全不同的方法（顺便说一句，看起来很有趣）。所有这些的测试程序可能真的很难或不可能确保结果。我将使用的真实数据集如此庞大和复杂，因此仅通过重复是不可能追踪任何错误的。也就是说，我需要对方法的可靠性 100% 满意，然后才能将其作为模块推送到大型代码中的位置。就目前而言 Niklas的方法更快，简单集合的答案当然是正确的。
但是，我如何确定它适用于真正的大型数据集？因为我将无法直观地跟踪错误！

更新 3： 请注意，对于这个问题，方法的可靠性比速度更重要。我希望最终能够将 Python 代码转换为 Fortran 以获得最大性能。

更新 4：
这篇文章有很多有趣的观点，并且慷慨地给出了答案，建设性的意见。我建议通读一遍。请接受我对问题的发展、惊人的答案以及建设性的评论和讨论的赞赏。

在 C++ 中重载“==”运算符时，是否有关于明确表示相等性的标准定义，或者有一组关于“==”应该如何表现的准则？

我目前有一个类不会将其整个自身存储在内存中。它基本上使用优先级队列来确定其内部对象被使用的频率，以及何时从队列末尾弹出对象，它们会从内存中删除并写入磁盘。

所以现在问题出现在相等上，这两个对象相等意味着什么。因为我们可以从在各个方面都相同的对象 A 和 B 开始，所以它们将相同的数据加载到内存中，并且它们在磁盘上具有相同的数据。但是在 A 和 B 上调用了一系列函数之后，它们现在可能会有所不同。A 和 B 在磁盘上仍然有相同的数据，但它们将不同的数据加载到内存中。所以问题是应该A == B解析为真还是假？

是否有一套规则或指南来定义这应该如何工作？或者这只是我决定什么对程序最有意义并记录“==”做什么的情况？

我有一个程序需要制作等价类并进行边界值分析。我的问题是，我们在课程中讨论的只是为直接输入整数或字符串的程序创建等价类。

该程序是一个带有日历的简单待办事项列表。用户唯一的键盘输入是任务的字符串和提醒时间的整数。

我知道如何处理整数，但字符串似乎有一个我无法找到的荒谬的最大大小。该输入也可以有任何符号等。

该程序唯一的其他方面是让您选择日期的按钮和让您选择月份和年份的下拉菜单。

如何为按钮和下拉菜单创建等价类，更不用说边界值分析了？另外，您如何制作等价类并对似乎没有无效输入的字符串进行边界值分析？

对于自动机算法，我需要使用函数式语言的快速 Union-Find 数据结构。由于我需要正式证明数据结构的正确性，所以我更喜欢简单的结构。

我想要做的是计算一个集合中元素的等价S类R ⊆ S × S。最后我想得到的是一些函数f: S → S，它将任何元素映射S到其R-equivalence 类的（规范）代表。通过“规范”，我的意思是我不在乎它是哪个代表，只要它对于一个等价类的所有元素都是相同的，即我想f x = f y ⟺ (x,y) ∈ R持有。

函数式语言中最好的数据结构和算法是什么？我应该补充一点，我真的需要“正常”功能代码，即没有可变性/状态转换器单子。

编辑：与此同时，我想出了这个算法：

这将创建一个映射，将 的任何元素映射S到其等价类的代表，其中代表是迭代到达的第一个元素S。我认为这实际上具有线性时间（如果地图操作是恒定的）。但是，我仍然对其他解决方案感兴趣，因为我不知道这在实践中的效率如何。

（我的关系在内部表示为“S → (S Set) option”，因此在 {t | (s,t) ∈ R} 上的迭代 - 这是对该结构的廉价操作。）

我试图理解这个主题并从非常基本的主题（不是离散域）开始，我认为这是不正确的。

我还不能发布图片，所以描述是这样的：

他们为负数定义了无效类，对 0-500 和 500 到 1300 有效，对 1300 到 5000 定义无效。
我认为这是一个错误，无效类以 5000 为界并趋于无穷大。我对么？