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