CODEWITHSUNDEEP
javaequivalence
zell
zell

Reputation: 10204

How to implement equivalence class in Java?

What would be the simple way to implement equivalence class in Java? Is there any library for that purpose?

The bothering part is how to write an efficient and non-naive "equal" operator.

Let S = {x,y,z,w,h}. If we use a mapping x->1, y->1, z->1, w->2, h->2 for the equivalence class of S, one has to consider the mapping x->10, y->10, z->10, w->20, h->20 as the same equivalence class.

Naive "equal" operator can quickly become time-consuming when the cardinal of the set S becomes large.

What would be the simple way? Any idea?

[EDITED] To clarify, the specific problem can be formalized as follows:

Let S be a non-empty set. We denote by M a set of partial mappings from V to integers. It is relatively easy to show that the binary relation \sim defined below derives an equivalence relation on M.

For m1 and m2 two partial mappings of M, m1 \sim m2 if and only if,

  1. for any a of V, m1(a) is defined if and only if m2(a) is defined

  2. for any a,b of V, m1(a) and m1(b) are both defined to be the same integer value 'z1' if and only if m2(a) and m2(b) are both defined to the same integer value 'z2' (which may or may not differ from 'z1')

    Example.

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

    But it is not correct to say

    a->5 \sim b->9

Thanks.

Upvotes: 1

Views: 2236

Answers (3)

Molhan Treeney
Molhan Treeney

Reputation: 1

Aside: I assume that the set S is actually the set V in your definition.

I think Uli is on the right track, although I would not assume that Set(Set(E)).equals() is efficient for your purposes. (Sorry, I couldn't get the lt or gt symbols to come through)

The default implementation of Set(E).equals() is likely O(nlog n) or O(n^2). Set(E).equals() almost certainly involves sorting; O(nlog n) is as good as it gets. I suggest you look at radix sort. It's O(n*log n), but grows very slowly.

Upvotes: 0

Niklas R
Niklas R

Reputation: 16870

If I understand you correct, you could apply vector normalization. A 3d vector for example is normalized to a length of 1 by dividing all of its components separately with the vectors length. If two normalized vector's components are equal, their original (non-normalized) vectors point in the same direction (which is what I think you define as 'equal')

x,y,z,w,h would in your case be a 5-dimensional vector. They belong to the same class when the show into the same direction, but may have an arbitrary length.

Upvotes: 2

ddmps
ddmps

Reputation: 4380

From what I understand from your question you can find the greatest common divisor (Euclid's algorithm recursively) for a set once and map the quotients with that instead - if they're exactly equal with another set it's equal, else not. This will only work if the sets are equal in size and mappings.

Upvotes: 2

Related Questions