MathGroup Archive 2006

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

Search the Archive

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?