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[1]:=
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[2]:=
myIntersection[{a, a, a, b, b, c}, {a, a, b, b}]
Out[2]=
{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[3]:=
c = Sort[Table[Random[Integer, {0, 9}], {10000}]];
d = Sort[Table[Random[Integer, {0, 9}], {12000}]];
In[4]:=
myIntersection[c, d];Timing
Out[4]=
{47.29 Second, Null}
Here time consumed is enormous, while of course ordinary Intersection is
almost instantaneous.
Tomas Garza
Mexico City