Grouping pairs - suggested tools

[Ian Kelly]

On Mon, Sep 20, 2010 at 5:09 PM, Alf P. Steinbach /Usenet <
alf.p.steinbach+usenet at gmail.com <alf.p.steinbach%2Busenet at gmail.com>>wrote:

> It seems to be the same problem as "equivalence sets".
>
> This problem was solved early on because e.g. Fortran compilers had to
> construct such sets (equivalence partitions of a set).
>
> I though I'd just say "Google it!", because I know there's a standard
> algorithm but I can't recall the name. However, googling it I found no
> mention of that algorithm. Not even in the Wikipedia articles on equivalence
> sets.
>

I don't recall the name either, but the standard algorithm represents the
equivalence sets as trees, with the canonical name of each set being
whatever happens to be at the root of tree.  To find the set containing any
given node, you just recurse up to the root of its tree (and then repoint
the links to the root on the way back down, to optimize for the next
lookup).  Merging two sets is then just a matter of hanging the root of one
set from the root of the other.  If memory serves, this algorithm is
amortized O(n) if the optimization is performed, where n is the total number
of merge and lookup operations.

Cheers,
Ian
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20100920/bc1cf346/attachment.html>