java - 如何在Java中实现等价类？

Question

在 Java 中实现等价类的简单方法是什么？有没有为此目的的图书馆？

麻烦的部分是如何编写一个高效且非天真的“相等”运算符。

让S = {x,y,z,w,h}. 如果我们x->1, y->1, z->1, w->2, h->2对 S 的等价类使用映射，则必须将映射x->10, y->10, z->10, w->20, h->20视为相同的等价类。

当集合 S 的基数变大时，幼稚的“相等”运算符会很快变得耗时。

什么是简单的方法？任何想法？

[编辑]为了澄清，具体问题可以形式化如下：

令 S 为非空集。我们用 M 表示一组从 V 到整数的部分映射。比较容易证明下面定义的二元关系 \sim 导出了 M 上的等价关系。

对于 m1 和 m2 M 的两个部分映射，m1 \sim m2 当且仅当，

1. 对于 V 的任何 a，当且仅当定义了 m2(a) 时，才定义 m1(a)

2. 对于 V 的任何 a,b，m1(a) 和 m1(b) 都被定义为相同的整数值 'z1' 当且仅当 m2(a) 和 m2(b) 都被定义为相同的整数值“z2”（可能与“z1”不同，也可能不同）

   例子。

   a->9,b->9,w->1 \sim a->10,b->10,w->0

   但是这样说是不对的

   a->5 \sim b->9

谢谢。

Answer 1

根据我从您的问题中了解到的情况，您可以找到一次集合的最大公约数（欧几里德算法递归），然后用它映射商 - 如果它们与另一个集合完全相等，则它相等，否则不相等。这仅在集合的大小和映射相等时才有效。

Answer 2

如果我理解正确，您可以应用矢量归一化。例如，通过将其所有分量分别除以向量长度，将 3d 向量归一化为长度 1。如果两个归一化向量的分量相等，则它们的原始（非归一化）向量指向同一方向（我认为您将其定义为“相等”）

x,y,z,w,h 在您的情况下将是一个 5 维向量。当显示方向相同时，它们属于同一类，但可以具有任意长度。

Answer 3

旁白：我假设集合 S 实际上是您定义中的集合 V。

我认为 Uli 走在正确的轨道上，尽管我不认为 Set(Set(E)).equals() 对您的目的有效。（抱歉，我无法让 lt 或 gt 符号通过）

Set(E).equals() 的默认实现可能是 O(n log n) 或 O(n^2)。Set(E).equals() 几乎可以肯定涉及排序；O(n log n) 尽可能好。我建议你看看基数排序。它是 O(n*log n)，但增长非常缓慢。