gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-11-29 03:37:05 25 4
gpt4 key购买 nike

在 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

谢谢。

最佳答案

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

关于java - Java中如何实现等价类?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14926490/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com