MathGroup Archive 2010

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

Search the Archive

Re: Generalizing Complement to handle multiple occurrences

  • To: mathgroup at smc.vnet.net
  • Subject: [mg112447] Re: Generalizing Complement to handle multiple occurrences
  • From: Leonid Shifrin <lshifr at gmail.com>
  • Date: Wed, 15 Sep 2010 20:03:40 -0400 (EDT)
  • References: <201009150838.EAA21715@smc.vnet.net>

Hi Mark,

The following will be pretty fast:

Clear[memberPositions];
memberPositions[x_List, y_List] :=
 Module[{tag},
  Pick[Range[Length[x]],
   Replace[x, Dispatch[Thread[Rule[Intersection[x, y], tag]]], {1}],
   tag]]

Clear[multComplement]
multComplement[x_, y_] :=
  Delete[x, List /@ memberPositions[x, Union[y]]];

In[5]:=
a={1,2,2,3,4,4,4,4};
b={3,5,7};

In[7]:= multComplement[a,b]
Out[7]= {1,2,2,4,4,4,4}

Performance test:

In[8]:=

la = RandomInteger[{1,20000},100000];
lb = RandomInteger[{1,20000},100000];

In[10]:= multComplement[la,lb]//Short//Timing

Out[10]=
{0.156,{2319,10829,2465,13044,18567,15250,11226,18576,<<638>>,1836,9996,15929,9805,15732,7853,2919,2070}}

The result comes out unsorted, in the order in which the elements were
originally stored in the first list. If this is a problem, just sort the
result.

Hope this helps.

Regards,
Leonid


On Wed, Sep 15, 2010 at 12:38 PM, Mark Coleman <markspcoleman at gmail.com>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
>
>


  • Prev by Date: Advice on Compile
  • Next by Date: Re: Inconsistent behaviour of Integrate
  • Previous by thread: Re: Generalizing Complement to handle multiple occurrences
  • Next by thread: Re: Generalizing Complement to handle multiple occurrences of elements