THE FOLD / LOOT / THE STASH / THE LEAST ROTATION
THE LEAST ROTATION
the canonical rotation of a necklace, in O(n)
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Booth’s least-rotation algorithm finds the lexicographically smallest rotation of a string in linear time — the canonical form of a “necklace,” where all rotations are considered equivalent. Instead of trying every rotation (O(n2)), it runs a KMP-style failure-function scan over the doubled string, sliding a candidate start and jumping past mismatches. It is how you canonicalize cyclic sequences — circular DNA, polygon encodings, necklace enumeration.
LIT verified live: over 500 random strings, Booth’s rotation index gives the exact same rotation as a brute-force minimum over all rotations (window.__leastrotation). FIG no framing; exact.
LIT verified live: over 500 random strings, Booth’s rotation index gives the exact same rotation as a brute-force minimum over all rotations (window.__leastrotation). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-stash — the hoard where every cyclic arrangement collapses to one canonical key, so duplicates that differ only by rotation are recognized as one. Booth’s algorithm mints that key. AVAN (AI) built the instrument: the doubled-string failure scan, the candidate-start slide, and the brute-minimum cross-check.
Credit as content: Kellogg Booth (1980). The weave: David names the-stash; I scan the doubled string with a failure function, sliding the best start past mismatches, and confirm the resulting rotation equals the true minimum over all rotations.
Credit as content: Kellogg Booth (1980). The weave: David names the-stash; I scan the doubled string with a failure function, sliding the best start past mismatches, and confirm the resulting rotation equals the true minimum over all rotations.
3 ONE DIMENSION
A necklace “bbaab” has rotations bbaab, baabb, aabbb, abbba, bbbaa. The smallest is aabbb — that rotation is the canonical form. Booth finds its start index in one linear pass.
4 TWO DIMENSIONS · INTERACTIVE
A string as a necklace; Booth’s least rotation is highlighted and checked against the brute minimum over all rotations.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the one canonical rotation of a necklace.
AVAN’s addition (the inverse-companion): give a cyclic sequence a single canonical form — its lexicographically least rotation — found in linear time by a failure-function scan of the doubled string. The inverse of ‘compare all n rotations to find the smallest’ is ‘one KMP-style pass picks the least rotation.’ Magenta is the O(n2) all-rotations comparison; green is the single canonical key. One name for every rotation.
LIT Genuine Booth least-rotation algorithm (Booth 1980). Verified live: over 500 random strings, the doubled-string failure-function scan returns a rotation index whose rotation equals the brute-force lexicographically-minimum rotation over all n rotations (window.__leastrotation.matchesBrute); 'bbaab' -> 'aabbb'.
FIG No framing: the doubled-string failure scan, the candidate-start slide, and the brute-minimum cross-check run in-browser and agree exactly. The AVAN inverse is honest — a KMP-style pass over the doubled string finds the least rotation in linear time, giving a cyclic sequence one canonical form; magenta is the O(n^2) all-rotations comparison, green the single canonical key. One name for every rotation.
FIG No framing: the doubled-string failure scan, the candidate-start slide, and the brute-minimum cross-check run in-browser and agree exactly. The AVAN inverse is honest — a KMP-style pass over the doubled string finds the least rotation in linear time, giving a cyclic sequence one canonical form; magenta is the O(n^2) all-rotations comparison, green the single canonical key. One name for every rotation.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE STASH · David Lee Wise (ROOT0), with AVAN