THE FOLD / LOOT / THE HOARD / THE PATIENCE SORTING
THE PATIENCE SORTING
deal cards to piles — the pile count is the longest increasing run
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Patience sorting is a solitaire-inspired algorithm: deal cards one at a time onto piles, each card landing on the leftmost pile whose top is ≥ it (or starting a new pile if none fits). Astonishingly, the number of piles you end with equals the length of the longest increasing subsequence of the deck — a card game computes a deep combinatorial quantity in O(n log n) via binary search.
Back-pointers between piles reconstruct the actual subsequence. This is the fast LIS algorithm, and the pile structure ties to the RSK correspondence and the Ulam–Hammersley problem on random permutations.
LIT verified live: for 500 random sequences, the number of patience piles equals the longest-increasing-subsequence length computed by an independent O(n²) method (window.__patiencesorting). FIG no framing; exact.
Back-pointers between piles reconstruct the actual subsequence. This is the fast LIS algorithm, and the pile structure ties to the RSK correspondence and the Ulam–Hammersley problem on random permutations.
LIT verified live: for 500 random sequences, the number of patience piles equals the longest-increasing-subsequence length computed by an independent O(n²) method (window.__patiencesorting). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-hoard — dealing the whole deck into sorted piles. Patience sorting is the hoard laid out so its deepest structure — the longest run — falls out as a pile count. AVAN (AI) built the instrument: the greedy pile placement by binary search, the longest-increasing-subsequence check, the recovered subsequence.
Credit as content: the name and the LIS connection are due to David Aldous & Persi Diaconis (1999); the pile idea is folklore from the card game. The weave: David names the hoard; I deal the cards greedily and show the pile count is exactly the longest increasing subsequence.
Credit as content: the name and the LIS connection are due to David Aldous & Persi Diaconis (1999); the pile idea is folklore from the card game. The weave: David names the hoard; I deal the cards greedily and show the pile count is exactly the longest increasing subsequence.
3 ONE DIMENSION
Cards dealt onto piles: each goes on the leftmost pile whose top is ≥ it. The pile tops always stay sorted, and a brand-new pile opens exactly when a card beats every current top.
4 TWO DIMENSIONS · INTERACTIVE
A shuffled sequence dealt into patience piles. The pile count equals the longest increasing subsequence, verified against a brute method, and the recovered subsequence is highlighted.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the piles, their tops a sorted sequence, their count the longest increasing subsequence.
AVAN’s addition (the inverse-companion): a greedy, local decision computes a global optimum. Each card goes on the leftmost feasible pile with no lookahead and no table — yet the pile count is exactly the longest increasing subsequence, because the tops stay sorted and a new pile opens precisely when a card exceeds all current tops, which happens exactly LIS-length times. The inverse of ‘a global optimisation’ is ‘a myopic card game.’ Magenta is the O(n²) dynamic-programming table the greedy never builds; green is the sorted pile-tops maintained by a single binary search. Greed is optimal here — one of the rare exact cases where looking only at the next step still finds the best whole.
LIT Genuine patience sorting and its LIS connection (Aldous & Diaconis 1999; folklore card game). Verified live: dealing each element onto the leftmost pile with top >= it (binary search), the number of piles equals the longest-increasing-subsequence length computed by an independent O(n^2) DP for 500 random sequences (window.__patiencesorting.pilesEqualLIS); [3,1,4,1,5,9,2,6] gives 4 piles = LIS 4.
FIG No framing: the greedy pile placement and the brute LIS check run in-browser and agree exactly. The AVAN inverse is honest — a greedy local decision (leftmost feasible pile) computes the global longest increasing subsequence exactly, because pile tops stay sorted and a new pile opens exactly LIS-length times; magenta is the O(n^2) DP the greedy avoids, green the sorted pile tops.
FIG No framing: the greedy pile placement and the brute LIS check run in-browser and agree exactly. The AVAN inverse is honest — a greedy local decision (leftmost feasible pile) computes the global longest increasing subsequence exactly, because pile tops stay sorted and a new pile opens exactly LIS-length times; magenta is the O(n^2) DP the greedy avoids, green the sorted pile tops.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE HOARD · David Lee Wise (ROOT0), with AVAN