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