Message Boards Message Boards

Longest Monotone Sequences

In any sequence of ten distinct real numbers,  there exists an increasing subsequence of four terms or a decreasing subsequence of four terms.
This assertion is an instance of the Erd?s -Szekeres theorem, (1913-1996) and (1911-2005) resp.
For example, the sequence {6, 4, 3, 2, 5, 8, 9, 7, 1, 10} contains the sequence 4, 5, 7, 10, (and other 16 such).
Of course, there are examples with more than four increasing terms. In fact, this sequence contains the larger subsequence 4, 5, 8, 9, 10. This lead us to consider the following problem:

Given a list of integers, find the longest subsequence of elements which monotonically increases.

Note we do not require the numbers to be different or of a certain amount. That makes the problem always soluble. Take for instance the list

 u = {11, -2, 14, 20, -2, 2, 8, -2, 5, -8, -4, 4, 15, 2, 13, 11, 20, -1, -2, -3};

Can you find the longest subsequence? This problem is taken care of in Mathematica by the function LongestCommonSequence. The following are examples on how to get subsequences fullfiling some criteria applied to the previous list (note the third one is not monotonous).

1.- longest increasing subsequence
 LongestCommonSequence[u, Sort[u]]

{-2, -2, 2, 8, 15, 20}

2.- longest decreasing subsequence
 LongestCommonSequence[u, Sort[u, Greater]]

{11, 8, 5, 4, 2, -1, -2, -3}

3.- longest sequence with prime elements (a negative prime is considered a prime)
 LongestCommonSequence[u, Select[u, PrimeQ]]

{11, -2, -2, 2, -2, 5, 2, 13, 11, -2, -3}

4.- longest increasing sequence with positive prime elements
 LongestCommonSequence[u,
 Select[Sort[u], Positive[#] \[And] PrimeQ[#] &]]

{2, 5, 13}

5.- longest increasing sequence with even elements
 LongestCommonSequence[u, Select[Sort[u], EvenQ[#] &]]

{-2, -2, 2, 8, 20}

and then this one gave me an idea,
 LongestCommonSequence[u, Reverse[u]]

{-2, 20, -2, 2, -2, 20, -2}

What about tackling the problem: given a string, find the longest-sized palindrome in the string? Take for example the string "abaacbcaaccaaabcba",
 u = Characters["abaacbcaaccaaabcba"];
LongestCommonSequence[u, Reverse[u]]

{"a", "b", "a", "a", "c", "c", "a", "a", "c", "c", "a", "a", "b", "a"}

this, however, is not acceptable as the characters are not adjacent, although they form a subsequence, they do not form a substring. Fortunatelly there is a suitable function to compute adjacent subsequences
 LongestCommonSubsequence[u, Reverse[u]]

{"a", "a", "c", "b", "c", "a", "a"}

As an example of its use, the following generates a random string of length 500 using the digits 0, 1 and 2 and finds the largest palindrome within it.

n = 500;
h = RandomInteger[{0, 2}, n];
s = LongestCommonSubsequence[h, Reverse[h]];
sst = StringJoin[ToString /@ s];
hst = StringJoin[ToString /@ h];
{{a, b}} = StringPosition[hst, sst];
Row[Table[
  Style[ToString[h[[i]]], Bold, If[a <= i <= b, Red, Gray]], {i, n}]]



CommonSubsequence performs reasonably fast.
 ListLinePlot[First /@ Table[Timing[
    h = RandomInteger[{0, 2}, n];
    LongestCommonSubsequence[h, Reverse[h]];], {n, 5000}]]

There is a built-in undocumented function:
In[1]:= LongestAscendingSequence[{1, 2, 3, 4, 6, 5, 8}]

Out[1]= {1, 2, 3, 4, 5, 8}
But I know that's not very helpful!
The built-in function is, of course, faster:
 In[2]:= u = RandomInteger[{1, 100000}, 100000];
 
 In[3]:= LongestCommonSequence[u, Sort[u]]; // AbsoluteTiming
 
 Out[3]= {0.319552, Null}
 
 In[4]:= LongestAscendingSequence[u]; // AbsoluteTiming
 
 Out[4]= {0.018221, Null}
POSTED BY: Patrick Stevens
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract