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: [mg70481] Re: Faster ways to unionize intersecting sets?
  • From: ab_def at prontomail.com
  • Date: Tue, 17 Oct 2006 02:59:24 -0400 (EDT)
  • References: <eg02a3$81m$1@smc.vnet.net>

lsha wrote:
> Hi,
>
> I need to search a list of sets and unionize any sets that intersect. The
> following functions seems to work but may be there are faster ways?
>
> Thanks in advance.
>
>
>
> intersectQ[s1_, s2_] := If[Intersection[s1, s2] != {}, True, False]
>
> mergeSets[s_List] := Module[
> {h, r, singles, club, cnt},
> cnt = Length[s];
> If[cnt < 2, Return[s]];
> singles = {};
> club = s;
>
> While[cnt >= 2,
> h = club[[1]];
> r = Rest[club];
> hit = 0;
> club = If[intersectQ[h, #], hit = 1; Union[h, #], #] & /@ r;
> If[hit == 0, singles = Append[singles, h]];
> --cnt;
> ];
> Join[singles, club]
> ]

Each sublist can be viewed as a chain of vertices in a graph; then
mergeSets effectively finds the connected components:

<<discretemath`
mergeSetsCC[$LL_] := Module[
  {LL = $LL, Lelem, Lpair, M, n},
  n = Length[Lelem = Union @@ LL];
  LL = LL /. Dispatch@ Thread[Lelem -> Range@ n];
  Lpair = Flatten[Partition[#, 2, 1]& /@ LL, 1];
  M = SparseArray[Lpair -> Array[1&, Length@ Lpair], {n, n}];
  M += Transpose@ M;
  Lelem[[#]]& /@ StrongComponents[M]
]

This is quite fast because of the efficient internal implementation of
StrongComponents:

In[3]:= data = Array[Random[Integer, {1, 2*10^5}]&, {10^4, 10}];
  Timing[mergeSetsCC[data];]

Out[4]= {0.562*Second, Null}

Maxim Rytin
m.r at inbox.ru


  • Prev by Date: Re: Re: Demostration
  • Next by Date: Re: Re: Demostration
  • Previous by thread: Re: Faster ways to unionize intersecting sets?
  • Next by thread: Re: Bessel K expansion, large argument?