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