Find the longest strictly increasing sequence in a scrambled stream by stacking cards into patience piles.
- Call the length of the longest run on six numbers before playing the shuffle
- Step the patience dealer to watch cards route into sorted piles
- Inspect the 2D dominance grid where chains climb northeast
- Take the boss round bet on whether two antichains can share a chain element
After thisYou will read diff engines, card-sorting metrics, and box-stacking posets as geometric chain decompositions.
Short on timeStep through the ChainAntichain panel to see why the pile count always equals the longest chain.
The Solitaire Shuffle
3 minthe hook
Every diff engine finds the longest increasing subsequence of matched line numbers and calls everything outside it an insertion or a deletion. Six numbers stand on a board in scrambled order: 4 1 5 2 6 3. Pick any subset, keep their left-to-right order, and require every chosen value to exceed its predecessor.
Enumerating the subsequences of a 100,000-element sequence means candidates, a 30,103-digit number. Patience sorting needs 1.66M comparisons. Lock in a guess at the longest ascending run hidden inside the six numbers.
In the sequence 4, 1, 5, 2, 6, 3, how long is the longest strictly increasing subsequence?
Plot the six numbers as the skyline: six points in the plane, where a chain that climbs northeast is an increasing subsequence. The panel deals the same numbers into the piles, the patience-sorting rows below the skyline.
The identity on the left is Mirsky's theorem (Mirsky 1971): the height of a poset equals the fewest antichains needed to cover it. The patience piles are exactly that cover — each pile is a decreasing subsequence, so an antichain. (The brief for this page attributed the identity to Dilworth; that is the common swap. Dilworth 1950 is the dual: min chain cover = max antichain = width.)
pile tops: [·, ·, ·] · number of piles = 0 = LIS of the first 0 cards
Six points (i, pᵢ). Gold: a longest increasing subsequence. Blue: a longest non-increasing one. The transport at the top steps the patience piles card by card.
Watch the piles as you step the deal: each card lands on a pile or starts a new one, and when the last number lands the pile count equals the length of the gold chain on the skyline. That equality is the quiet miracle of the page. It is a theorem of partially ordered sets, not an accident of arithmetic.
NextWhy does brute-force enumeration face a 30,103-digit count of candidate sequences?
The Quadratic Illusion
2 minthe trap
The naive programmatic strategy tracks a state array: let dp[i] denote the length of the longest increasing subsequence terminating at index i.
Evaluating this recurrence demands scanning every prior position for each element, consuming pairwise comparisons. But this recurrence does not actually care about strings or arrays; it is secretly computing the maximal chain in a geometric order.
NextHow does patience sorting partition the sequence into a minimal set of descending piles?
The 2D Dominance Poset
2 minthe invariant
Drop the array index and treat the sequence as a cloud of planar points . Define a partial order by requiring both coordinates to grow simultaneously:
This relation is the intersection of two linear orders—the order of arrival and the order of value—forming a two-dimensional dominance poset.
A chain in this poset is a collection of mutually comparable points: sorting them by position automatically sorts them in strictly increasing value. An antichain is a set of mutually incomparable points: sorting them by position yields a sequence that never ascends ( whenever ).
The height of the poset is the size of its largest chain, while its width is the size of its largest antichain. In the visualizer above, gold is the maximal chain and blue is the maximal antichain.
NextHow does Dilworth's theorem link antichain pile counts to the maximum chain length?
Mirsky, Dilworth, and the Patience Invariant
2 minthe algebra
Mirsky’s Theorem (Mirsky 1971). In any finite partially ordered set, the height equals the minimum number of antichains needed to cover all elements.
Patience sorting provides a constructive proof of Mirsky’s theorem. Deal the cards left to right, placing each card onto the leftmost pile whose visible top is at least the card’s value; if no such pile exists, start a new pile to the right.
Every pile formed this way is strictly non-increasing in time order, so each pile is an antichain. Whenever a card lands on pile , it can be linked to the current top of pile , carving out an ascending chain whose length matches the pile count.
After dealing any number of cards, examine the top cards of all active piles from left to right. What ordering invariant do they obey?
Because the active pile tops remain strictly sorted, finding the leftmost valid pile costs only one binary search per card. For cards, patience sorting computes the exact LIS in time, entirely sidestepping the quadratic recurrence.
What about Dilworth’s theorem? It is the dual counterpart to Mirsky’s result, not a duplicate.
Dilworth’s Theorem (Dilworth 1950). In any finite partially ordered set, the width equals the minimum number of chains needed to cover all elements.
Mirsky partitions into antichains to reveal the height; Dilworth partitions into chains to reveal the width.
Erdős–Szekeres Theorem (Erdős & Szekeres 1935). Every sequence containing more than distinct elements must contain either an increasing subsequence of length or a non-increasing subsequence of length .
For r = 4 and s = 4, any sequence with more than 9 numbers must have an ascending run of 4 or a descending run of 4. Test this on: 3, 2, 1, 6, 5, 4, 9, 8, 7, 0 (ten numbers). Which run does the bound deliver?
NextHow does binary search across pile tops extract the LIS in n log n comparisons?
Two Algorithms, One Invariant
2 minthe simulation
Consider a nine-element sequence where the primal chain and the dual antichain diverge in length.
The identity on the left is Mirsky's theorem (Mirsky 1971): the height of a poset equals the fewest antichains needed to cover it. The patience piles are exactly that cover — each pile is a decreasing subsequence, so an antichain. (The brief for this page attributed the identity to Dilworth; that is the common swap. Dilworth 1950 is the dual: min chain cover = max antichain = width.)
pile tops: [·, ·, ·, ·, ·, ·] · number of piles = 0 = LIS of the first 0 cards
Nine points. The gold chain has length 6 and the pile count is 6 — Mirsky's antichain cover. The blue antichain has length 3 and the greedy chain cover also has 3 chains — Dilworth's dual. Six and three, from one set of points.
Step through the deal. The gold chain is 2 → 5 → 7 → 8 → 10 → 13 of length 6, and exactly 6 piles emerge; this is Mirsky’s theorem in action. Meanwhile, the longest non-increasing antichain is 11 → 8 → 6 of length 3, and the points can be covered by 3 chains; this confirms Dilworth’s dual.
Now observe the same sequence evaluated by dynamic programming.
Hover or click a cell: its predecessor cells light up and the exact recurrence that filled it appears here. Or press play to walk the fill order(9 cells in dependency order).
dp[i] = 1 + max{ dp[j] : j < i and seq[j] < seq[i] }, and dp[i] = 1 when that set is empty.
Longest strictly increasing subsequence (length ending at each position).
The O(n²) table. Hover a cell to see the exact recurrence that filled it, or step the fill order and watch the back-pointers.
The DP table outputs 1 2 2 3 4 4 5 6 3. Its maximum entry is 6, identical to the pile count produced by patience sorting. Two distinct computational paradigms converge upon the same structural invariant.
1 minboss round
Consider the sequence with duplicate values: [3, 3]. How long is its longest strictly increasing subsequence, and how many patience piles does it produce?
NextWhere does patience sorting power modern diff engines and flight interception paths?
Box Stacking, Diff Engines, and Interception
2 minsystems
The height of a two-dimensional poset governs real-world systems constrained by dual thresholds.
Box nesting models this directly: box nests inside box when both dimensions are strictly smaller, turning maximum tower height into an LIS chain. Similarly, missile defence scheduling uses Mirsky’s theorem to calculate the minimum number of non-increasing interception batteries needed to neutralize an inbound missile barrage.
In file comparison algorithms, diff engines locate identical lines between two documents, order them by line number, and find the longest increasing subsequence. The elements outside that LIS identify the exact insertions and deletions.
Beyond the First Row: Young Tableaux and Random Matrices
Patience sorting reveals just the first row of a richer algebraic structure. Applying the Robinson–Schensted correspondence (Schensted 1961) inserts each number into a Young tableau. The length of the first row equals the LIS, while the length of the first column equals the longest decreasing subsequence.
For random permutations of size , the expected LIS length scales asymptotically as (Vershik & Kerov 1977).
Baik, Deift & Johansson (1999) proved that the fluctuations of the LIS around converge to the Tracy–Widom distribution from random matrix theory. A simple card game connects directly to quantum energy levels.
Attributions
- Mirsky 1971 — A dual of Dilworth’s decomposition theorem: poset height equals the minimum antichain cover size.
- Dilworth 1950 — A decomposition theorem for partially ordered sets: poset width equals the minimum chain cover size.
- Erdős & Szekeres 1935 — A combinatorial problem in geometry: Ramsey-theoretic lower bounds for monotonic subsequences.
- Schensted 1961 — The Robinson–Schensted correspondence relating subsequences to Young tableaux.
- Baik, Deift & Johansson 1999 — Proof of Tracy–Widom fluctuations for the LIS of random permutations.