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

Question

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

麻烦的部分是如何编写一个高效且非简单的“等于”运算符。

令 S = {x,y,z,w,h}。如果我们对 S 的等价类使用映射 x->1, y->1, z->1, w->2, h->2 ，则必须考虑映射 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，m1(a)被定义当且仅当m2(a)被定义

2. 对于 V 的任意 a,b，m1(a) 和 m1(b) 都定义为相同 当且仅当同时定义了 m2(a) 和 m2(b) 时，整数值 'z1' 到相同的整数值'z2'(可能与 'z1')

   例子。

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

   但是这样说不是对的

   a->5\sim b->9

谢谢。

Answer 1

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