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



• Prev by Date: Re: Troubleshooting Mathematic's Help
• Next by Date: RE: Troubleshooting Mathematic's Help