Services & ResourcesWolfram ForumsMathGroup Archive

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

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>