问题标签 [equivalence-classes]

假设我有一个自定义数据结构Data，它揭示了两个相关属性：tag指示该项目属于哪个等价类，并rank指示该项目有多好。

我有一组无序的Data对象，并且想要检索n最高的对象rank- 但每个等价类最多有一个对象。

（同一等价类中的对象不一定比较相等，也不一定具有相同的rank，但我不希望输出中的任何两个元素来自同一类。换句话说，产生的关系这些等价类不是==。）

我的第一种方法看起来像这样：

• 按降序对列表进行排序rank
• 创建一个空集s
• 对于列表中的每个元素：
  • 检查它tag是否在s；如果是这样，请继续
  • 将其添加tag到s
  • 产生那个元素
  • 如果我们已经产生了n元素，请停止

但是，这感觉很尴尬，好像应该有一些更好的方法（可能使用itertools高阶函数）。结果n元素的顺序并不重要。

这个问题的 Pythonic 解决方案是什么？

玩具示例：

我最近开始学习 ocaml 并且无法解决问题。

目标：

给定一个整数列表和一个函数，根据给定函数将整数排序为等价类，作为另一个列表中的列表。等价列表的顺序必须与原始列表中给出的顺序相同。

更新：我决定尝试让它在没有库功能的情况下工作。

到目前为止，这是我的代码。它编译但不运行。任何有关语法的帮助将不胜感激。

重要提示：这是一个家庭作业问题，所以我不是在寻找为我粘贴的代码。我试图在我的家中通过它对整体思维过程和语法有所帮助。一旦我得到它的工作，我会努力使它更有效率

我正在开发一个群论证明器。现在，我有兴趣证明如果 H 和 K 是子群，那么 H 与 K 相交是子群。我的证明基于构建一个关系（==H），使得

h (==H) g 当且仅当 hg^{-1} 属于 H。证明这是一个等价关系（自反、对称、传递）等价于证明 H 是一个子群。

我已经完成了以下代码，当我尝试证明 H intersect K 是一个子组时，我失败了。我是 Prolog 的新手，所以也许我遇到了一些基本错误。在数学证明中不需要说等价关系的显式形式，因此我省略了它。

在程序中，我将 hg 和 kg 表示为 H 和 K。H 相交 K 是 hkg。

目前，它没有通过反身性测试（第一次测试）。你能告诉我这个程序有什么问题吗？如果您需要更多说明，请随时询问。

我有一个 csv 文件，其中每一行都包含一对值。例如，它可能看起来像这样：

每一行都应该被解释为这两个值应该在同一个组中。我正在尝试找到一种优雅/简单的方法来从 csv 中获取有序对并确定分组。根据上面的对，这些组将是 {A, B, D}, {C, H}, {E, F, G}，我想输出如下内容：

我很难找到解决这个问题的最佳方法。有没有一种简单的方法可以做到这一点？

我所拥有的： set 上的等价关系{1,...,n}，作为等价对的完整列表给出(a,b)（这已经是传递的；不需要计算传递闭包）。n很大（比如说，最多几百万）；等效对的总数最多O(n)（通常要少得多），并且单个等效类很小（我没有这个数字，但是说O(log n)）。

我想要的是：一种单独枚举所有等价类的方法，即依次获取每个等价类的全套元素；最多具有复杂性O~(n)（在我的代码中执行的所有其他计算都是，如果可能的话O(n log(n))，我绝对不想在该大小上做任何二次方）。

使用union-find 结构将有助于构建传递闭包（我不需要），但我相信，这对构建等价类没有帮助。我还可以轻松地计算（比如说）每个类中的最小代表（只需扫描完整的等价关系，直到找到它），甚至及时存储它们O(n)（构建一个 1...n 的恒等向量，然后扫描完整的等价关系关系，如果可能，用最小值替换）；但是，这对于枚举等价类也没有多大帮助。

这个问题是否存在经典解决方案？

在某些正则表达式的风格中，在方括号表达式中，=符号是一个特殊字符，用作分隔符，用于将任何一个等价类中的元素括起来。该文档说明了以下内容：

等价类表达式应表示属于等价类的整理元素集，如整理顺序中所述。只应识别初级等价类。该类应通过将等价类中的任何一个整理元素括在括号相等（“[=”和“=]”）分隔符中来表示。例如，如果 'a'、'à' 和 'â' 属于同一个等价类，则 "[[=a=]b]"、"[[=à=]b]" 和 "[[ =â=]b]" 都等价于 "[aàâb]"。如果整理元素不属于等价类，则等价类表达式应视为整理符号。

我不太确定这意味着什么。如果a和属于à同â一个等价类，这是否意味着我们希望指定正则表达式"[ab]"和是等价的"[àb]"？"[âb]"那么使用[= =]分隔符的目的是什么，因为我们还不如写"[aàâb]"？

我理解“等价类”在其一般定义中的含义，但我无法理解它在这种情况下的含义。

我有一个List[String]. 我想按给定的等价关系对其进行分组：

我已经尝试过 method groupBy，但我无法将空字符串放在单独的组中。

我更喜欢任何等价关系的答案f(x: String, y: String): Boolean，而不仅仅是这个。

编辑：我没有指定，但输入类型是真的List[String]，不是List[(String, String)]，f是 a binary relation，这就是为什么它有 2 个字符串输入，并且预期的返回类型是List[List[String]]

编辑：正如@a​​ndrey-tyukin 所提到的，f它不是等价关系，所以要求“任何等价关系的答案”是无稽之谈。

编辑：一个例子：

• "a" == "a"，这就是为什么他们在同一个组
• 虽然是“”==“”，但是f会导致false，所以他们不在同一个组

我在下面有一个方法isPerfect(x)（带4<=x<=10000），如何根据等价类、边界值和基路径测试编写测试用例：