MathGroup Archive 2004

[Date Index] [Thread Index] [Author Index]

Search the Archive

Computing sets of equivalences

  • To: mathgroup at
  • Subject: [mg46437] Computing sets of equivalences
  • From: Mariusz Jankowski<mjankowski at>
  • Date: Wed, 18 Feb 2004 00:37:03 -0500 (EST)
  • Organization: University of Southern Maine
  • Sender: owner-wri-mathgroup at

Dear Mathgroup, I think this falls into the "classic algorithms" category,
so I hope some of you will find this interesting. I checked archives and
mathsource but did not find anything useful.

I have a list of lists, each sublist implying an equivalence. I am trying to
split the list into lists of equivalences (this is part of a connected
components algorithm).  For example, given


I want


Here is my currently "best" attempt. I accumulate the equivalences by
comparing pairs of list, merging them if they have common elements. At the
end of each iteration I remove all merged pairs from original list and

         If[Intersection[tmp,x[[i]]]==={}, tmp, tmp=Union[tmp,x[[i]]];
           pos=Join[pos, {{i}}]], {i, 2, Length[x]}];
       x=Delete[x, pos];
       y=Join[y, {tmp}] ];

Can you tell me if you have or know of a realization of this classic
operation that works better/faster? Are there alternative paradigms for
solving this kind of problem.

Thanks, Mariusz

  • Prev by Date: A New Kind of Science Online
  • Next by Date: Re: Bloomberg and Mathematica
  • Previous by thread: RE: A New Kind of Science Online
  • Next by thread: Re: Computing sets of equivalences