Enumerating longest increasing subsequences and patience sorting
作者： Sergei Bespamyatnikh , Michael Segal
DOI: 10.1016/S0020-0190(00)00124-1
关键词:
摘要: Abstract In this paper we present three algorithms that solve combinatorial optimization problems related to each other. One of them is the patience sorting game, invented as a practical method real decks cards. The second problem computing longest monotone increasing subsequence given sequence n positive integers in range 1,…,n . third enumerate all subsequences permutation.
acm.org
elsevier.com
uni.wroc.pl 参考文章(8)
R. Baeza-Yates, G. H. Gonnet, Handbook of algorithms and data structures : in Pascal and C Addison-Wesley. ,(1991)
Donald Ervin Knuth, Sorting and Searching ,(1973)
C. Schensted, Longest Increasing and Decreasing Subsequences Canadian Journal of Mathematics. ,vol. 13, pp. 299- 311 ,(1961) , 10.1007/978-0-8176-4842-8_21
James W. Hunt, Thomas G. Szymanski, A fast algorithm for computing longest common subsequences Communications of the ACM. ,vol. 20, pp. 350- 353 ,(1977) , 10.1145/359581.359603
David Aldous, Persi Diaconis, Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem Bulletin of the American Mathematical Society. ,vol. 36, pp. 413- 432 ,(1999) , 10.1090/S0273-0979-99-00796-X
Michael L. Fredman, On computing the length of longest increasing subsequences Discrete Mathematics. ,vol. 11, pp. 29- 35 ,(1975) , 10.1016/0012-365X(75)90103-X
P. van Emde Boas, Preserving order in a forest in less than logarithmic time and linear space Information Processing Letters. ,vol. 6, pp. 80- 82 ,(1977) , 10.1016/0020-0190(77)90031-X
Donald Ervin Knuth, The Art of Computer Programming ,(1968)