Re: Delete elements from list..
- To: mathgroup at smc.vnet.net
- Subject: [mg116762] Re: Delete elements from list..
- From: Ray Koopman <koopman at sfu.ca>
- Date: Sat, 26 Feb 2011 06:08:45 -0500 (EST)
If the errors are relatively small then interpolating to the sorted x from the sorted y might be about as accurate as more complex schemes. On Fri, 25 Feb 2011 at 12:39:12 -0600, DrMajorBob <btreat1 at austin.rr.com> wrote: > It's possible the OP really wants the "longest increasing subsequence". > In that case, this is simple and fast for large lists: > > lisLS[x_List] := > Tally[#][[All, 1]] &@LongestCommonSequence[x, Union@x]; > > lisLS@{1, 9, 2, 3, 4, 5, 6, 7, 8} > > {1, 2, 3, 4, 5, 6, 7, 8} > > largestTst = RandomInteger[{1, 35000}, 40000]; > > Length@(one = lisLS[largestTst]) // Timing > > {0.067601, 393} > > That's due to Leonid Shifrin, I think. > > Bobby > > On Fri, 25 Feb 2011 05:36:31 -0600, Ray Koopman <koopman at sfu.ca> wrote: > >> On Feb 24, 3:29 am, "Maarten van der Burgt" >> <Maarten.VanDerBu... at kla-tencor.com> wrote: >>> Hallo, >>> >>> Thanks everybody who replied to my questions. >>> >>> The real problem I have is just a bit more complex than my >>> simplified example. My list is in fact a numerical 2D list like >>> mylist1 == {{x_0, y_0}, {x_1,y_1},... {x_i, y_i}, ...{x_N, y_N}}. >>> The xi are strictly increasing and the yi should be as well. >>> Due to some measurement errors it can happen that this is not the >>> case. I simply want to delete the {xi, yi} pairs where >>> y_i <== y_i-1. That way I end up with a list, mylist2, >>> where also the y_i are strictly increasing. >>> (that way I can make an Interpolation[Reverse/@mylist2] >>> in order to have a function x_i(y_i)). >>> >>> I have not had the time to study your answers in this view, >>> but from a first look and the variety of the answers it seems >>> that there is definitely something which should help. >>> >>> Thanks for your help. >>> >>> Maarten >> >> Your rule would you reduce {1, 9, 2, 3, 4, 5, 6, 7, 8} to {1, 9} >> which I don't think you would want to do. >> >> Wouldn't it make more sense to delete only the 9? >> >> (If we work from right to left instead of left to right, >> deleting the current y if it's >= min[all previous kept y_i], >> we do delete only the 9.) >> >> Shouldn't the question be more like "What is the smallest set of >> points that must be deleted to make y monotone increasing in x?" >> >> Or, considering that all the y_i may contain error, you could find >> the vector z that is closest to y (in some sense that depends on the >> assumed nature of the errors) and is also monotone increasing in x, >> and then do inverse interpolation. >> > -- > DrMajorBob at yahoo.com