Re: Delete elements from list..

*To*: mathgroup at smc.vnet.net*Subject*: [mg116783] Re: Delete elements from list..*From*: Ray Koopman <koopman at sfu.ca>*Date*: Sun, 27 Feb 2011 04:36:18 -0500 (EST)

On Sat, 26 Feb 2011 at 21:19:39 +0100, "Maarten van der Burgt" <Maarten.VanDerBurgt at kla-tencor.com> wrote > Ray, > > You are correct: my rule would reduce {1, 9, 2, 3, 4, 5, 6, 7, 8} to > {1, 9}. > But as the y_i data are generally strictly increasing with only a few % > or less of the points where the y_i make a dip, this is not a problem. > > Maarten I didn't mean to suggest that your data would be as extreme as the example I gave. I mostly wanted to make the point that monotonicity is a symmetric concept, and there is no reason why it should not be evaluated from right to left. It turns out that it matters: the two directions pick systematically different sets of points. Here are two routines that select monotone x,y pairs: monup works from left to right, mondo works from right to left. monup = Compile[{{x,_Real,1},{y,_Real,1}}, (* going up *) Module[{i, j, m, n, rs}, n = Length@x; j = 1; m = y[[j]]; rs = Table[{0.,0.},{n}]; rs[[j]] = {x[[j]],m}; Do[ If[y[[i]] > m, m = y[[i]]; rs[[++j]] = {x[[i]],m}], {i,2,n}]; Take[rs,j]]] mondo = Compile[{{x,_Real,1},{y,_Real,1}}, (* going down *) Module[{i, j, m, n, rs}, n = Length@x; j = n; m = y[[j]]; rs = Table[{0.,0.},{n}]; rs[[j]] = {x[[j]],m}; Do[ If[y[[i]] < m, m = y[[i]]; rs[[--j]] = {x[[i]],m}], {i,n-1,1,-1}]; Take[rs,{j,n}]]] Generate some sample data: x = N@Range[n = 1000]; f = Sqrt; y = f@x + RandomReal[NormalDistribution[],n]; Plot it, along with four different monotone lines: the true function (green), monup & mondo (red & black), and the nameless function (blue) that I described in my post last night. If speed and closeness to the green line are the important criteria then the blue line has much to recommend it. ListPlot[Transpose@{x,y}, PlotRange->All, Frame->True, Axes->None, AspectRatio->1, Prolog-> {Thickness[.005], Red, Line@monup[x,y], Green, Line@Transpose@{x,f@x}, Blue, Line@Transpose@{x,Sort@y}, Black, Line@mondo[x,y], PointSize[.005]}, ImageSize->450{1,1}] > > -----Original Message----- > From: Ray Koopman [mailto:koopman at sfu.ca] > Sent: Friday, 25 February, 2011 12:37 > To: mathgroup at smc.vnet.net > Subject: [mg116732] Re: Delete elements from list.. > > On Feb 24, 3:29 am, "Maarten van der Burgt" <Maarten.VanDerBu...@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.