Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: how to get the longest ordered sub sequence of a list

• To: mathgroup at smc.vnet.net
• Subject: [mg103227] Re: [mg103158] how to get the longest ordered sub sequence of a list
• From: DrMajorBob <btreat1 at austin.rr.com>
• Date: Fri, 11 Sep 2009 05:25:08 -0400 (EDT)
• References: <200909090845.EAA05996@smc.vnet.net>
• Reply-to: drmajorbob at yahoo.com

The following can be modified to do what you want. It mimics  
LongestIncreasingSubsequence from Combinatorica, but much faster.

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

One way to use it for decreasing subsequences is to Reverse twice:

Reverse@singleLongestIncreasing@Reverse@originalList

However, this is a code for Integer lists, and it finds STRICTLY  
increasing sublists only.

To get around that, consider an example with repeats:

s = RandomInteger[{0, 10}, 25]
s2 = Ordering@Ordering@s
Ordering@s == Ordering@s2
s[[Ordering@s2]] == Sort@s

{3, 5, 5, 6, 8, 8, 7, 10, 8, 8, 8, 0, 4, 10, 2, 7, 4, 7, 3, 10, 6, 2, \
10, 4, 3}

{4, 10, 11, 12, 17, 18, 14, 22, 19, 20, 21, 1, 7, 23, 2, 15, 8, 16, \
5, 24, 13, 3, 25, 9, 6}

True

True

The idea is that s and s2 sort the same way, but s2 is Integer with no  
repeats. The same thing happens if we start with real numbers:

s = RandomReal[{0, 10}, 25]
s2 = Ordering@Ordering@s
Ordering@s == Ordering@s2
s[[Ordering@s2]] == Sort@s

{9.36262, 3.15484, 5.93621, 7.32264, 8.48407, 5.30091, 6.85566, \
3.35133, 3.01294, 9.43156, 6.48782, 0.719399, 9.77835, 9.8369, \
9.70456, 8.39239, 6.25382, 2.75411, 0.572293, 2.25703, 6.57412, \
1.02859, 6.53337, 5.17617, 7.48962}

{21, 7, 11, 17, 20, 10, 16, 8, 6, 22, 13, 2, 24, 25, 23, 19, 12, 5, \
1, 4, 15, 3, 14, 9, 18}

True

True

So... to find a non-decreasing subsequence of s, find a strictly  
increasing subsequence of s2, and use the result as an index.

Back to an integer example, so that we can visually check it:

s = RandomInteger[{0, 10}, 25]
pairs = Sort@Transpose@{s2 = Ordering@Ordering@s, s}
pairs[[singleLongestIncreasing@s2]][[All, 2]]

{6, 6, 2, 3, 4, 10, 3, 8, 2, 7, 2, 0, 7, 8, 1, 8, 5, 0, 8, 1, 6, 9, \
6, 7, 9}

{{1, 0}, {2, 0}, {3, 1}, {4, 1}, {5, 2}, {6, 2}, {7, 2}, {8, 3}, {9,
   3}, {10, 4}, {11, 5}, {12, 6}, {13, 6}, {14, 6}, {15, 6}, {16,
   7}, {17, 7}, {18, 7}, {19, 8}, {20, 8}, {21, 8}, {22, 8}, {23,
   9}, {24, 9}, {25, 10}}

{2, 3, 3, 7, 7, 8, 8, 8, 9, 9}

or, a one-liner:

Sort[s][[singleLongestIncreasing@Ordering@Ordering@s]]

{2, 3, 3, 7, 7, 8, 8, 8, 9, 9}


or, a bit faster:

s[[t = Ordering@s]][[singleLongestIncreasing@Ordering@t]]

{2, 3, 3, 7, 7, 8, 8, 8, 9, 9}

To get a strictly increasing subsequence, when there are repeats... I'm  
not sure, since

Tally[%][[All, 1]]

{2, 3, 7, 8, 9}

may not be the longest such.

Bobby

On Wed, 09 Sep 2009 03:45:59 -0500, a boy <a.dozy.boy at gmail.com> wrote:

> how to get a (strict or not-strict)decreasing sub sequence of a list?
>                                              ----------------
> increasing                                   ?
>


-- 
DrMajorBob at yahoo.com

• References:
  • how to get the longest ordered sub sequence of a list in
    • From: a boy <a.dozy.boy@gmail.com>