MathGroup Archive 2009

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

Search the Archive

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
>
>
>
>   



  • Prev by Date: Re: Re: random variable
  • Next by Date: Re: Re: how to get the longest ordered sub
  • Previous by thread: Re: Re: how to get the longest ordered sub
  • Next by thread: Credit card balance transfer fee problem