On Mon, Sep 20, 2010 at 5:09 PM, Alf P. Steinbach /Usenet < alf.p.steinbach+use...@gmail.com <alf.p.steinbach%2buse...@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
-- http://mail.python.org/mailman/listinfo/python-list