Longest Increasing Scattered Subsequence
المؤلف:
Erdős, P. and Szekeres, G.
المصدر:
"A Combinatorial Problem in Geometry." Compos. Math. 2
الجزء والصفحة:
...
1-11-2020
829
Longest Increasing Scattered Subsequence
The longest increasing scattered subsequence is the longest subsequence of increasing terms, where intervening nonincreasing terms may be dropped. Finding the largest scattered subsequence is a much harder problem. The longest increasing scattered subsequence of a partition can be found using LongestIncreasingSubsequence[p] in the Wolfram Language package Combinatorica` . For example, the longest increasing scattered subsequence of the permutation ![<span style=]()
{6,3,4,8,10,5,7,1,9,2}" src="https://mathworld.wolfram.com/images/equations/LongestIncreasingScatteredSubsequence/Inline1.gif" style="height:15px; width:159px" /> is ![<span style=]()
{3,4,5,7,9}" src="https://mathworld.wolfram.com/images/equations/LongestIncreasingScatteredSubsequence/Inline2.gif" style="height:15px; width:77px" />, whereas the longest contiguous subsequence is ![<span style=]()
{3,4,8,10}" src="https://mathworld.wolfram.com/images/equations/LongestIncreasingScatteredSubsequence/Inline3.gif" style="height:15px; width:69px" />.
Any sequence of 
distinct integers must contain either an increasing or decreasing scattered subsequence of length 
(Erdős and Szekeres 1935; Skiena 1990, p. 75).
REFERENCES:
Erdős, P. and Szekeres, G. "A Combinatorial Problem in Geometry." Compos. Math. 2, 464-470, 1935.
Schensted, C. "Longest Increasing and Decreasing Subsequences." Canad. J. Math. 13, 179-191, 1961.
Skiena, S. "Longest Increasing Subsequences." §2.3.6 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 73-75, 1990.
الاكثر قراءة في نظرية الاعداد
اخر الاخبار
اخبار العتبة العباسية المقدسة
