       Re: Intersection and element counts

• To: mathgroup at smc.vnet.net
• Subject: [mg20672] Re: [mg20615] Intersection and element counts
• From: "Tomas Garza" <tgarza at mail.internet.com.mx>
• Date: Sun, 7 Nov 1999 02:10:07 -0500
• Sender: owner-wri-mathgroup at wolfram.com

```Arturas Acus [acus at itpa.lt] wrote:

> I am interesting in intersecion, which takes into
> account the number of the same elements.
>
> It is I would like
>
> myIntersection[{a,a,a,b,b,c},{a,a,b,b}]
>
> to give me {a,a,b,b}.
>
> Any solutions?
> Do theoretical speed of this function is
> very different of usual intersection algorithm speed?

I have a solution which takes quite a long time  -- perhaps it can be
improved, certainly in elegance but also in time consumption. Still, the
problem itself is very time consuming, anyway. Let the two sets of symbols
be A and B.

In:=
myIntersection[A_List, B_List] :=
Module[{Ap = Split[Sort[A]], Bp = Split[Sort[B]]},
ulti[x_List] := If[Length[x] == 0, {}, Last[x]];
desc[x_List] := Table[Take[x, j], {j, 1, Length[x]}];
Flatten[Table[
Table[ulti[Intersection[desc[Ap[[j]]], desc[Bp[[i]]]]], {j, 1,
Length[Ap]}], {i, 1, Length[Bp]}]]]

In:=
myIntersection[{a, a, a, b, b, c}, {a, a, b, b}]
Out=
{a, a, b, b}

In order to test for speed I produced two sets of integers between 0 and 9,
one with 10,000 elements, the other with 12000.
In:=
c = Sort[Table[Random[Integer, {0, 9}], {10000}]];
d = Sort[Table[Random[Integer, {0, 9}], {12000}]];

In:=
myIntersection[c, d];Timing
Out=
{47.29 Second, Null}

Here time consumed is enormous, while of course ordinary Intersection is
almost instantaneous.

Tomas Garza
Mexico City

```

• Prev by Date: RE: LU factorization in Mathematica
• Next by Date: Re: LU factorization in Mathematica
• Previous by thread: Re: Intersection and element counts
• Next by thread: Re: Re: Intersection and element counts