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
>
>
- References:
- Generalizing Complement to handle multiple occurrences of elements
- From: Mark Coleman <markspcoleman@gmail.com>
- Generalizing Complement to handle multiple occurrences of elements