       Computing sets of equivalences

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

```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

{{1,2},{1,5},{2,3},{3,4},{5,6},{7,8},{11,12},{12,13},{10,14}}

I want

{{1,2,3,4,5,6},{7,8},{10,14},{11,12,13}}.

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
repeat.

iselectEquivalences[v_]:=Module[{x,y,tmp,pos},
x=v;y={};
While[x=!={},
tmp=x[];
pos={{1}};
Do[
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}] ];
y]

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