Complexity of set partition generation while equivalence relation is given
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.