Re: Re: how to get the longest ordered sub sequence of a
- To: mathgroup at smc.vnet.net
- Subject: [mg103261] Re: [mg103181] Re: how to get the longest ordered sub sequence of a
- From: DrMajorBob <btreat1 at austin.rr.com>
- Date: Fri, 11 Sep 2009 19:57:08 -0400 (EDT)
- References: <h87pgp$5gt$1@smc.vnet.net> <200909101118.HAA17784@smc.vnet.net>
- Reply-to: drmajorbob at yahoo.com
Valeri, Here's your example: list = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 7, 9, 8, 9}; sp = Split[list, OrderedQ[{#1, #2}] &] pos = Ordering[sp, 1, (Length[#1] >= Length[#2]) &] // First sp[[pos]] {{3}, {1, 4}, {1, 5, 9}, {2, 6}, {5}, {3, 5, 7, 9}, {8, 9}} 6 {3, 5, 7, 9} That's the longest CONSECUTIVE non-decreasing subsequence. Clear[zeroPad, singleLongestIncreasing] zeroPad[{}] = {0}; zeroPad[x_List] := x singleLongestIncreasing[x_List] := Module[{t = Append[x, 1 + Max[x]], len, pred, path, max}, path[i_Integer, o___Integer] /; pred[i] != {} := path[Last@pred@i, i, o]; len[i_] := len[i] = Module[{mx, prior, pick, nxt = t[[i]]}, pick = Pick[Range[i - 1], Take[t, i - 1] - nxt, _?Negative]; prior = len /@ pick; mx = Max@zeroPad@prior; pred[nxt] = t[[Pick[pick, prior, mx]]]; 1 + mx]; len /@ Range@Length@t; Most[path@Last@t /. path -> List] ] singleLongestIncreasing@list {1, 2, 3, 5, 7, 8, 9} And that's a maximal non-decreasing subsequence (not necessarily the only one). The more general sort is sometimes called a "scattered" subsequence. Bobby On Thu, 10 Sep 2009 06:18:19 -0500, Valeri Astanoff <astanoff at gmail.com> wrote: > On 9 sep, 10:37, a boy <a.dozy.... at gmail.com> wrote: >> how to get a (strict or not-strict)decreasing sub sequence of a list? >> = > ---------------- >> >> increasing = > ? > > Good day, > > Just an example of what you can do : > > In[1]:= list = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 7, 9, 8, 9}; > > In[2]:= sp = Split[list, OrderedQ[{#1, #2}] &] > Out[2]= {{3}, {1, 4}, {1, 5, 9}, {2, 6}, {5}, {3, 5, 7, 9}, {8, 9}} > > In[3]:= pos = Ordering[sp, 1, (Length[#1] >= Length[#2]) &] // First > Out[3]= 6 > > In[4]:= sp[[pos]] > Out[4]= {3, 5, 7, 9} > > hth > > -- > Valeri Astanoff > -- DrMajorBob at yahoo.com
- References:
- Re: how to get the longest ordered sub sequence of a list in
- From: Valeri Astanoff <astanoff@gmail.com>
- Re: how to get the longest ordered sub sequence of a list in