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?
>
>
>
>
> 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?