Re: Re: how to get the longest ordered sub
- To: mathgroup at smc.vnet.net
- Subject: [mg103254] Re: [mg103212] Re: [mg103158] how to get the longest ordered sub
- From: Fred Simons <f.h.simons at tue.nl>
- Date: Fri, 11 Sep 2009 07:36:39 -0400 (EDT)
- References: <200909101124.HAA18266@smc.vnet.net>
Finding a longest increasing subsequence seems to be a much more
complicated problem than finding the longest segment on which the
sequence is increasing. Bob's solution is short and elegant, but needs
all subsets of the list and therefore can be used only for small lists,
up to about length 17.
Because of I could not think of anything better, I wrote a small
backtracking solution for this problem.
Finding only one longest increasing subsequence is much easier than
finding all longest subsequences. For example, consider the sequence
(4,5,6,1,2,3,7,8,9). Every increasing subsequence starting with 5 or 6
gives an increasing subseqence starting with 4, just by replacing the
first number with 4. Therefore, when we have computed the longest
increasing subsequence starting with 4 and when we need only one longest
increasing subsequence, we may skip the computation of the longest
increasing subsequences starting with 5 and 6. That is implemented in
the following code. The variable n is the depth of the backtracking; for
every n the first n-1 numbers of res are the beginning of the increasing
subsequence under construction and aux[n] is the list of the numbers
that can be used at position n.
lst = RandomInteger[{1, 1000}, 100]
Timing[n=1;
aux[1]=lst;
While[Length[aux[1]]>=2 &&aux[1][[1]]>=aux[1][[2]],aux[1]=Rest[aux[1]]];
res=Array[0&,Length[lst]];
sol={};
While[n>1 || aux[1]!={},
If[aux[n]!={}&&Length[aux[n]]+n>Length[sol],
res[[n]]=aux[n][[1]];
aux[n+1]=Select[aux[n],#>res[[n]]&];
While[aux[n]!={}&&aux[n][[1]]>=res[[n]],aux[n]=Rest[aux[n]]];
n=n+1,
aux[n]={};
If[n>1,n=n-1];
If[Length[sol]<n,sol=Take[res,n]];
res[[n]]=0]];
sol]
For a list of length 100 we find a longest increasing subsequence in
about 2 seconds.
Fred Simons
Eindhoven University of Technology
Bob Hanlon wrote:
> lst = {1, 8, 2, 4, 3, 5};
>
> Select[oss = Select[Subsets[lst], OrderedQ],
> Length[#] == Max[Length /@ oss] &]
>
> {{1, 2, 4, 5}, {1, 2, 3, 5}}
>
> Select[oss = Select[Subsets[lst], OrderedQ[Reverse[#]] &],
> Length[#] == Max[Length /@ oss] &]
>
> {{8, 4, 3}}
>
>
> Bob Hanlon
>
> ---- a boy <a.dozy.boy at gmail.com> wrote:
>
> =============
> Thank all! your answers are right!
> However,what I need is the longest not-strict ordered items of a given list
> L, not a segment of L. For example,
> {1,8,2,4,3,5} -- ascending--> {1,2,4,5}
> {1,8,2,4,3,5} --descending-->{8,4,3}
>
> Because when I think this question (
> http://groups.google.com/group/comp.soft-sys.math.mathematica/browse_thread/thread/f82401b1a517310c/9ca72a83a2313f50?lnk=gst&q=a.dozy.boy#9ca72a83a2313f50
> ):
> For any integer k and 3^k, suppose 2^j is the closest to 3^k,
> Gap[k]=| 3^k-2^j| is the subtraction .
>
> Gap = Function[k, x = k*Log[2, 3]; Min[3^k - 2^Floor[x], 2^Ceiling[x] -
> 3^k]];
> list=Table[{i, Gap[i]}, {i, 1, 5000}]
>
> I want to find a non-strict decreasing items of {Gap[i]} .
>
>
> On Wed, Sep 9, 2009 at 7:53 PM, Fred Simons <f.h.simons at tue.nl> wrote:
>
>
>> a boy wrote:
>>
>>
>>> how to get a (strict or not-strict)decreasing sub sequence of a list?
>>> ----------------
>>> increasing ?
>>>
>>>
>>>
>>>
>>>
>> lst=RandomInteger[{1,100}, {5000}];
>>
>> With[{sublists=Split[lst, #1<#2&]},
>> With[{m=Max[Length /@ sublists]},
>> Select[sublists, Length[#]==m&]]]
>>
>> {{3,19,22,33,51,66,89,95}}
>>
>> Fred Simons
>> Eindhoven University of Technology
>>
>>
>
> --
>
> Bob Hanlon
>
>
>
>
- References:
- Re: how to get the longest ordered sub sequence of a
- From: Bob Hanlon <hanlonr@cox.net>
- Re: how to get the longest ordered sub sequence of a