MathGroup Archive 1999

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

Search the Archive

Re: Intersection and element counts

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

Arturas Acus [acus at] 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.

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]}];
        Table[ulti[Intersection[desc[Ap[[j]]], desc[Bp[[i]]]]], {j, 1,
            Length[Ap]}], {i, 1, Length[Bp]}]]]

myIntersection[{a, a, a, b, b, c}, {a, a, b, b}]
{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.
c = Sort[Table[Random[Integer, {0, 9}], {10000}]];
d = Sort[Table[Random[Integer, {0, 9}], {12000}]];

myIntersection[c, d];Timing
{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