Re: Re: how to get the longest ordered sub
- To: mathgroup at smc.vnet.net
- Subject: [mg103244] Re: [mg103212] Re: [mg103158] how to get the longest ordered sub
- From: Leonid Shifrin <lshifr at gmail.com>
- Date: Fri, 11 Sep 2009 05:28:15 -0400 (EDT)
- References: <200909101124.HAA18266@smc.vnet.net>
Hi,
On Thu, Sep 10, 2009 at 3:24 PM, Bob Hanlon <hanlonr at cox.net> 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}}
>
This method works but has exponential complexity in the size of the list,
both in
time and memory consumption, so can not realistically be used for lists
larger
than say 15-20 elements.
If a single longest increasing subsequence is sufficient (rather than
listing all),
there is a much more efficient alternative - to use the fact that longest
increasing
subsequence is the longest common subsequence of the initial sequence and
the sorted one:
In[1] =
lst = {2, 1, 6, 3, 10, 4, 5, 6, 15, 7, 20, 8, 9, 11};
In[2] = Select[oss = Select[Subsets[lst], OrderedQ],
Length[#] == Max[Length /@ oss] &] // Timing
Out[2] = {0.282, {{2, 3, 4, 5, 6, 7, 8, 9, 11}, {1, 3, 4, 5, 6, 7, 8, 9,
11}}}
In[3] = LongestCommonSequence[lst, Sort[lst]] // Timing
Out[3] = {0., {1, 3, 4, 5, 6, 7, 8, 9, 11}}
This one should have a quadratic complexity of the underlying LCS
algorihtm, plus we take an additional speed advantage of LCS being
implemented
internally in Mathematica.
It can be made even more efficient (asymptotically) if needed (n log n ).
Regards,
Leonid
>
> 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