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