Complexity of set partition generation while equivalence relation is given Given a binary equivalence relation, R on a set A, Let P be the resulting partition. I want to generate the partition means each subset in the partition. What would be the fastest algorithm for this purpose? please help.
The binary equivalence relation induces an undirected graph: each item corresponds to a vertex, and draw an edge between each pair of equivalent items.  Now compute the connected components of this graph (this can be done in linear time using algorithms based on DFS).  Each connected component is a single subset in the partition.