Re: Delete elements from list..
- To: mathgroup at smc.vnet.net
- Subject: [mg116752] Re: Delete elements from list..
- From: DrMajorBob <btreat1 at austin.rr.com>
- Date: Sat, 26 Feb 2011 06:06:56 -0500 (EST)
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...@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