Enumerating Longest Increasing Subsequences and Patience Sorting Study
Explore the detailed study on enumerating longest increasing subsequences, patience sorting, and combinatorial optimization problems, including algorithms and applications discussed in the paper by Sergei Bespamyatnikh and Michael Segal. Dive into the concepts of van Emde Boas tree, index operations, and practical methods for sorting decks of cards. Discover insightful information on computing and enumerating monotonous increasing subsequences from a given sequence or permutation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Enumerating longest increasing subsequences and patience sorting Sergei Bespamyatnikh and Michael Segal Information Processing Letters Volume 76, Issues 1 2, 20 November 2000, Pages 7-11 Presenter: Shin-Cheng Lin Date: Apr. 6, 2021
Abstract In this paper we present three algorithms that solve three combinatorial optimization problems related to each other. One of them is the patience sorting game, invented as a practical method of sorting real decks of cards. The second problem is computing the longest monotone increasing subsequence of the given sequence of n positive integers in the range 1, , n. The third problem is to enumerate all the longest monotone increasing subsequences of the given permutation.
1.Longest increasing subsequence van Emde Boas tree insert(i) insert the number i into S delete(i) delete the number i from S next(i) get the successor of i in S prev(i) get the predecessor of i in S In O(loglogn) time
1.Longest increasing subsequence L[i] is defined by longest increasing subsequence that ends on some element of that is smaller than Siand has been considered before.
1.Longest increasing subsequence (7, 9, 2, 8, 8, 6, 8, 5 ) L (1, ) T (7, ) Index of prev(7) = nil, L[1]=1 next(7) = nil
1.Longest increasing subsequence (7, 9, 2, 8, 8, 6, 8, 5 ) L (1, 2 ) T (7, 9 ) Index of prev(9) = 1, L[2]=1+L[1]=2 next(9) = nil
1.Longest increasing subsequence (7, 9, 2, 8, 8, 6, 8, 5 ) L (1, 2, 1 ) T (2, 7, 9 ) => (2, 9 ) Index of prev(2) = nil, L[3]=1 Index of next(2) = 1 , L[3]==L[1], delete next(2) from T
1.Longest increasing subsequence (7, 9, 2, 8, 8, 6, 8, 5 ) L (1, 2, 1, 2 ) T (2, 8, 9 ) => (2, 8) Index of prev(8) = 3, L[4]=1+L[3]=2 Index of next(8) = 2 , L[4]==L[2], delete next(2) from T
1.Longest increasing subsequence (7, 9, 2, 8, 8, 6, 8, 5 ) L (1, 2, 1, 2, 2) T (2, 8) Index of prev(8) = 3, L[5]=1+L[3]=2 Index of next(8) = nil
1.Longest increasing subsequence (7, 9, 2, 8, 8, 6, 8, 5 ) L (1, 2, 1, 2, 2, 2) T (2, 6, 8) => (2, 6) Index of prev(6) = 3, L[6]=1+L[3]=2 Index of next(6) = 8 , L[6]==L[4], delete next(6) from T
1.Longest increasing subsequence (7, 9, 2, 8, 8, 6, 8, 5 ) L (1, 2, 1, 2, 2, 2, 3) T (2, 6, 8) Index of prev(8) = 6, L[7]=1+L[6]=3 Index of next(8) = nil
1.Longest increasing subsequence (7, 9, 2, 8, 8, 6, 8, 5 ) L (1, 2, 1, 2, 2, 2, 3, 2) T (2, 5, 6, 8) => (2, 5, 8) Index of prev(5) = 3, L[8]=1+L[3]=2 Index of next(5) = 6 , L[8]==L[6], delete next(5) from T
1.Longest increasing subsequence insert(i), delete(i), next(i), prev(i) in O(loglogn) n element O(n loglogn)
2.Enumerate all LIS left1(j) is the largest index i , such that L[i]=L[j], i < j. S[i] is the end of other LIS. left2(j) is the largest index i , such that L[i]=L[j]-1, i < j. S[i] is the previous element of current LIS.
2.Enumerate all LIS Recursive and DFS S (7, 9, 2, 8, 8, 6, 8, 5) L (1, 2, 1, 2, 2, 2, 3, 2)
2.Enumerate all LIS Constructing tables of left1 and left2 needs O(n). K LISs and the length of each LIS is l(S). O(n+Kl(S))
3.Patience sorting Patience sorting: Take a deck of cards labeled 1, 2, 3, , n. The deck is shuffled, cards are turned up one at a time and dealt into piles on the table, according to the rule: A card with a low index may be placed on a card with a higher index, or may be put into a new pile to the right of the existing piles. The target of the game is to finish with as few piles as possible.
3.Patience sorting Let T be the data structure of van Emde Boas For each Si : Insert Siinto T If next(Si) nil, delete next(Si), meaning that Si is placed on top of next(Si) O(n loglogn)
