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