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

```

• Prev by Date: FourierCosTransform
• Next by Date: Automate datafitting to a series of parameterized function
• Previous by thread: Re: Faster ways to unionize intersecting sets?
• Next by thread: Re: Faster ways to unionize intersecting sets?