MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

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



  • 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