Patience sort and the Longest increasing subsequence

Patience sort and the Longest increasing subsequence

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".

In case that sounds heavy going, the authors kick off with a card game.

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. The object of the game is to finish with as few piles as possible.

Read full article from Patience sort and the Longest increasing subsequence