Re: programming problem about elements taken
- To: mathgroup at smc.vnet.net
- Subject: [mg72472] Re: programming problem about elements taken
- From: Peter Pein <petsie at dordos.net>
- Date: Sun, 31 Dec 2006 04:58:58 -0500 (EST)
- References: <en5evt$l12$1@smc.vnet.net>
Barrow schrieb:
> Dear all,
> I have a list of numbers (A),in fact, they are numbers distributed
> over [0,1]. Given parameter \epsilon, I have to choose elements from A
> such that their distances are larger than \epsilon, so the elements are
> "distringuishable". My goal is to find the maximum number of elements
> from A to meet the above "distinct criterion".
> How to do it with the functions build-in in mathematica ??
> Thanks in advence. Sincerely Barrow
>
Hi Barrow,
the first method coming to my mind has been the use of ReplaceRepeated, but
for long lists this lasts far too long:
A=Table[Random[],{2000}];
epsilon=1.*^-4;
Timing[Length[
r1=A//.{x___,c_,y___}/;Min[Abs[c-{x,y}]]<epsilon:>{x,y}
]]
--> {22.125 Second,1650}
It is sufficient to compare element k with elements k+1,...,n:
selectDistinguishable[a_List,eps_]:=
Pick[a,Min[Abs[a[[#]]-Drop[a,#]]]>eps&/@Range[Length[a]]]
Timing[Length[
r2=selectDistinguishable[A,epsilon]
]]
--> {0.11 Second,1650}
_Much_ better :-)
r1===r2
--> True
hth,
Peter