MathGroup Archive 2010

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

Search the Archive

Re: Generalizing Complement to handle multiple occurrences of elements

  • To: mathgroup at smc.vnet.net
  • Subject: [mg112458] Re: Generalizing Complement to handle multiple occurrences of elements
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Thu, 16 Sep 2010 05:59:41 -0400 (EDT)

Mark Coleman wrote:
> Greetings,
> 
> I'm wondering how one can efficiently generalize the built-in
> Complement function to return multiple occurrences of elements. For
> instance, the current version generates
> 
> a={1,2,2,3,4,4,4,4}
> b={3,5,7}
> 
> Complement[a,b]={1,2,4}
> 
> I'm looking for a way to define
> 
> myComplement[a,b]={1,2,2,4,4,4,4}
> 
> My current code is very inefficient!
> 
> Thanks,
> 
> Mark
> 

Could use DeleteCases. Except it is currently a bit slow if the second 
list is large. Here is a variant that is faster. (I was asked this 
in-house not too long ago, hence already had code available.)

deleteCasesPatternFree[l1_List, l2_List] := Module[
   {hh, seq},
   Map[(hh[#] = True) &, l2];
   Table[
     If[TrueQ[hh[l1[[j]]]], seq, l1[[j]]], {j, Length[l1]}] /.
    seq -> Sequence[]
   ]

Example:

n = 5;
l1 = RandomInteger[10^n, 2*10^n];
l2 = RandomInteger[10^n, 5*10^(n-1)];

In[12]:= Timing[res2 = deleteCasesPatternFree[l1,l2];]
Out[12]= {0.525921, Null}

In the development kernel this is quite fast, so I'll show that as well.

In[13]:= Timing[res1 = DeleteCases[l1, Alternatives @@ l2];]
Out[13]= {0.114982, Null}

In[14]:= res1===res2
Out[14]= True

Daniel Lichtblau
Wolfram Research



  • Prev by Date: Re: Generalizing Complement to handle multiple occurrences
  • Next by Date: Re: Colorfunction in ContourPlot
  • Previous by thread: Re: Generalizing Complement to handle multiple occurrences of elements
  • Next by thread: Re: Tabulating expressions dependent on two variables