Re: programming problem about elements taken

*To*: mathgroup at smc.vnet.net*Subject*: [mg72488] Re: [mg72470] programming problem about elements taken*From*: danl at wolfram.com*Date*: Mon, 1 Jan 2007 04:07:07 -0500 (EST)*References*: <200612301039.FAA21673@smc.vnet.net>

> 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 > If the list can be large, and the epsilon small (so many elements get used), then something reasonably fast can be done from the sorted list. For speed I found it best to use Compile[] and split off a part that that function cannot handle. Note that this is in effect a greedy alghorithm. It starts by taking the smallest element in the list, then takes the first thereafter that differs from that smallest by more than epsilon, then the first thereafter differing from the next selected element by more than epsilon, etc. It is not hard to show that this will give a resulting set of maximal size. distinctElementsC = Compile[{{ll, _Real, 1}, {eps, _Real}}, Module[ {sll = Sort[ll], el = -1.}, Table[ If[sll[[j]] - el > eps, el = sll[[j]]; el, -1.], {j, 1, Length[sll]}] ]]; distinctElements[ll_, eps_] := distinctElementsC[ll, eps] /. -1. -> Sequence[] In[66]:= ll = Table[Random[], {10^6}]; In[67]:= Timing[de = distinctElements[ll, .000001];] Out[67]= {2.584, Null} If you require elements to retain their order in the original list then you can still attain reasonable speed using a second pass, with hashing, to figure out the ordering. Daniel Lichtblau Wolfram Research