Re: Faster ways to unionize intersecting sets?

*To*: mathgroup at smc.vnet.net*Subject*: [mg70270] Re: Faster ways to unionize intersecting sets?*From*: "dkr" <dkrjeg at adelphia.net>*Date*: Wed, 11 Oct 2006 01:53:15 -0400 (EDT)*References*: <eg02a3$81m$1@smc.vnet.net><eg2e4o$70u$1@smc.vnet.net> <eg81ph$mqh$1@smc.vnet.net>

Here is a functional programming approach to your problem. It is not necessarily any faster than your procedural approach, but is more in the spirit of how Mathematica programming is normally done. In[1]:= intersectQ[s1_, s2_] := If[Intersection[s1, s2] =!= {}, True, False]; g[t1_List,t2_List]/;intersectQ[t1,t2]:=(hit=1;Union[t1,t2]); g[t1_List,t2_List]:=t2; mergeSetsAlt[s:{__List}]:= Module[{z,part1x,restx}, Reap[Nest[ Function[x,hit=0;part1x=x[[1]];restx=Rest[x]; z=(g[part1x,#]&/@restx); If[hit==0,Sow[part1x];z,z]],s, Length[s]]][[2,1]]]; In[5]:= s1={{1,2},{2,3},{4,5},{6,7},{7,5},{9,10},{11,12},{13,14}}; mergeSetsAlt[s1] Out[6]= {{1,2,3},{4,5,6,7},{9,10},{11,12},{13,14}} The g function essentially substitutes for your If function, the Reap/Sow construct handles your saving of the singles via Append, and Nest essentially substitutes for While. In cases where you have a large number of sets, most containing a large number of elements, the following alternative version of intersectQ may be faster: intersectAltQ[s1_List, s2_List] := If[Cases[s1, a_ /; MemberQ[s2, a], {1}, 1] =!= {}, True, False]; Since all you want to determine is whether the two sets intersect, it is not necessary to compute the entire Intersection[s1,s2]. As soon as intersectAltQ finds the first common element, it stops. dkr