Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2011

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Delete elements from list..
  • Next by Date: Re: weibull plot on weibull scaled paper
  • Previous by thread: Re: Delete elements from list..
  • Next by thread: Re: Delete elements from list..