Skip to main content

Alogorithm: Finding Longest Increasing Subsequence using Patience Sort in C#

Finding the Longest Increasing Sequence is an interesting problem and there are multiple solutions available with varying time complexity. The solution that i plan to share today is the uses of Patience Sort  to find such a sequence. The solution finds a particular longest increasing sub-sequence as the original sequence may contain more than one such sequence.

In 1999 The Bulletin of the American Mathematical Society published a paper by David Aldous and Persi Diaconis entitled: “Longest Increasing Subsequences: From Patience Sorting to the Baik-Deift-Johansson Theorem”.

I have implemented this solution in C# and derived it from this excellent article which provides a Python implementation for the same.

This is how patience sort works

  • 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 low card may be placed on a higher card (e.g. 2 may be placed on 7), or may be put into a new pile to the right of the existing piles.
  • At each stage we see the top card on each pile. If the turned up card is higher than the cards showing, then it must be put into a new pile to the right of the others. 
I have left out the part that returns the sorted list of numbers as it is not relevant for the longest sub-sequence problem.

The first thing to note here is
Once the cards\numbers are organized into piles. The total number of piles denote the size of longest sub-sequence.
 To get the longest sequence some extra book keeping is required. According to the paper

    Lemma 1. With deck π, patience sorting played with the greedy strategy ends with exactly L(π) piles. Furthermore, the game played with any legal strategy ends with at least L(π) piles. So the greedy strategy is optimal and cannot be improved by any look-ahead strategy.

    Proof. If cards a1 < a2 < … < al appear in increasing order, then under any legal strategy each ai must be placed in some pile to the right of the pile containing ai-1, because the card number on top of that pile can only decrease. Thus the final number of piles is at least l, and hence at least L(π). Conversely, using the greedy strategy, when a card c is placed in a pile other than the first pile, put a pointer from that card to the currently top card c′ < c in the pile to the left. At the end of the game, let al be the card on top of the rightmost pile l. The sequence a1 ← a2 ← … ← al-1 ← al obtained by following the pointers is an increasing subsequence whose length is the number of piles.

What this means is whenever a card is added to a stack (except first stack), the card should keep a back pointer to the topmost card on the pile on the left.

To get a better understanding of the above logic, i have created a diagram detailing the links that get created during the patience sort process for the list of numbers

31,16,7,39,5,12,32,18,9,1


The longest increasing sub-sequence using the above algorithm is
5,12,18
The gist for the implementation is available here



Comments

Popular posts from this blog

Caching Images downloaded from web on Windows Phone Isolated storage

I was helping on a Windows Phone application where the requirement was to cache the images the phone downloads on the isolated storage for offline viewing.
I wanted a solution which was simple and as transparent as possible. While researching I found  someone wrote a Silverlight converter for loading images from isolated storage. Taking that as a base I created a converted which can
Load image from web (http + https), and persist it to isolated storage.In case of network connectivity issues can load the same image from isolated storage. It does that by mapping the http url to a isolated storage location.In case the network is down and the image is neither there in cache, loads a default image, passed as parameter to converter.Here is the gist for the implementation.


To use the converter
Import the name space.Declare the converter as resource.Set the Image Source Property to use this converter like this 

AngularJS Model - ViewModel

Recently Robin Ward did a comparison between AngularJS and Ember (both the post and the comments are interesting read). One of the complaint that Robin had that AngularJS does not provide any specialized model class. As described in the blog

There is no standard Model base class, nor is there a component or interface in AngularJS that defines what a model is supposed to be.
What that means is that anything defined on $scope can acts as model, as this sample on the blog describes




For some (like me) this is the flexibility where as for others who want a more structural approach this is a nuisance.AngularJS does not even provide any definite guidelines around how the model should be actually designed to be effective with AngularJS

This leads to what we call as $scope pollution. We define multitude of properties on the $scope object and managing it becomes difficult.  Looking at the code one cannot tell what is the actual model and what properties are just to support UI logic.

Model Desig…