CODEWITHSUNDEEP
algorithmsearch
Shikarn-O
Shikarn-O

Reputation: 3417

Clever algorithm for checking on equality

We need to implement next feature:

Suppose we have a list of some objects.
We need to say what objects are the same and what are not.
Suppose 1 is equal to 2 and 2 is equal to 5.
So 1 is equal to 5 and we don't need to check them.

Does this algorithm exist?
Any ideas would be very great.

Upvotes: 1

Views: 815

Answers (3)

japreiss
japreiss

Reputation: 11251

You want a Disjoint Set strucutre with path compression. It's very simple to implement, and the performance is close to O(1).

Upvotes: 1

FUD
FUD

Reputation: 5184

I think this can be thought of as having sets of elements which are equal. And IMO Disjoint Set Data Structure will be very efficient in maintaing such set of records. The basic idea is to first put every element as a seperate set, whenever you encounter a equality relation you take the set to which those elements belong and merge them. The run time for merge and lookup are sub-logarithmic if you use path compression. http://en.wikipedia.org/wiki/Disjoint-set_data_structure

Upvotes: 3

Peter Alexander
Peter Alexander

Reputation: 54270

If you have a graph where the vertices are the objects and there's an edge between known equal objects, then every object connected to another object is also equal. So, to test if object A equals object B, you are testing if a path exists between A and B in that graph.

You can use any graph searching algorithm to do this. Depth-first search would be a good start.

If you want to find all connected pairs then you could use Tarjan's algorithm to find all strongly connected components. Within each component, all objects are equal.

Upvotes: 0

Related Questions