Skip to content

Collection table

A paged table over a combinatorial collection, rendered by <notatio-collection-table>. Every collection head — Subsets, SymmetricGroup, IntegerPartitions, DyckPaths, and the rest of the catalog — is a lazy indexed family: Count is closed-form and At unranks, so the table draws a page by asking for twenty indices and never touches the other rows. That is the whole design: SymmetricGroup(20) has 2.4 × 10¹⁸ rows and pages exactly as fast as Subsets(4), and the # column is the index that reproduces each row (At(expr, #)).

The controls are live. Columns are statistics applied to the row: a head (Descents, Inversions, CycleCount, …) or any expression over the row _ (Max(_) - Min(_)). Filter is a predicate over _, answered the way Filter is — by testing rows — so it has to scan the source; the scan runs in the background, bounded, and the match count is exact only once it has covered every row. Sorting by a column has to materialise that column, so it is bounded too and the table says which prefix it ordered. Click a column header to sort; click again to flip; a third time to clear.

Subsets, with the glyph

Subsets(4), every subset drawn

Sixteen rows, in the binary (Gray-free) order the kernel unranks. Sort by Length to group by size; filter Length(_) == 2 for the six pairs — the count goes exact at once, since sixteen rows scan in a millisecond. The Sum column is any expression over the row, not just a head.

source
<notatio-collection-table expr="Subsets(4)" columns="Length, Sum" glyph="subset" page-size="10" />

Permutations and their statistics

SymmetricGroup(5), the classical statistics

The 44 derangements of five, picked out of 120 by the filter, each with its Descents number, MajorIndex, Inversions count and Cycles count. Clear the filter to see all 120; sort by Inversions to see that it and MajorIndex are equidistributed but not equal; add Peaks, Excedances or LeftToRightMaxima as further columns.

source
<notatio-collection-table expr="SymmetricGroup(5)" columns="Descents, MajorIndex, Inversions, CycleCount, FixedPoints" glyph="permutation" filter="FixedPoints(_) == 0" />

SymmetricGroup(12) — paging without materialising

479,001,600 permutations. The pager opens on page one million — At unranks the ten rows there directly. Type a page number, or jump to the last page with ». Sorting here orders only the first two thousand rows (the bound is adjustable) and says so; a filter scans twenty thousand rows at a time and offers to continue.

source
<notatio-collection-table expr="SymmetricGroup(12)" columns="Descents, Inversions" glyph="permutation" page="1000000" page-size="10" />

Beyond 2⁵³

SymmetricGroup(20)

2,432,902,008,176,640,000 rows — past Number.MAX_SAFE_INTEGER, so the count shows as approximate and the pager stops at the last exactly-indexable page. The kernel counts and unranks in doubles; indexing past 2⁵³ would silently round, so the table refuses rather than guess. readonly hides the editors.

source
<notatio-collection-table expr="SymmetricGroup(20)" columns="Descents, CycleCount" page-size="10" readonly />

Other carriers

IntegerPartitions(8) as Ferrers diagrams

Partitions unrank in reverse-lexicographic order. The partition statistics come from @enumeratio/statistics, where each is a definition over the part list; filter IsSelfConjugate(_) == 1 for the two self-conjugate partitions of 8, or Length(_) == 3 for the five into three parts.

source
<notatio-collection-table expr="IntegerPartitions(8)" columns="Length, LargestPart, DistinctParts, DurfeeSquare, Crank" glyph="partition" page-size="10" />

DyckPaths(4) as step words

Fourteen paths (Catalan), as up/down words drawn as mountain ranges. Height, Area, Returns (touches of the axis) and Hills are Dyck-path statistics; sort by Returns to see the Narayana-like split, or filter Returns(_) == 1 for the five primitive paths.

source
<notatio-collection-table expr="DyckPaths(4)" columns="Height, Area, Returns, Hills" glyph="dyck" page-size="14" />

SetPartitions(4), blocks as pills

Fifteen set partitions (Bell). The element is the block list; the glyph converts it to the restricted-growth string the set-partition figure draws. Length counts blocks — sort by it to walk from one block to four — and Max(Map(Length, _)) is the largest block. (The named set-partition statistics, Blocks, SingletonBlocks, …, are declared over list<integer> today and reject a ragged block list; they land here once they carry their own carrier type.)

source
<notatio-collection-table expr="SetPartitions(4)" columns="Length, Max(Map(Length, _))" glyph="set-partition" page-size="15" />

What the bounds are for

The three operations have three different costs, and the table is honest about each:

  • Paging is At — closed-form unranking, constant per row. Any page of any collection.
  • Filtering is Filter — a scan of the source, linear in how far it has to look. The scan runs in time slices so the page stays responsive, stops at scan-limit rows (twenty thousand by default) and offers to go on. The count reads "k matches in the first N of M" until the scan is complete, then "k of M match".
  • Sorting by a statistic needs the statistic for every candidate row, which is the one thing a lazy collection cannot give you for free. It is bounded by sort-limit, and the note above the table says when the order covers only a prefix.

The compute-engine's own Filter has the same linear cost, plus an iteration cap (ce.iterationLimit, 1024 by default) after which Count(Filter(…)) stays symbolic and At(Filter(…), i) answers Missing — so the table drives the scan itself, by index, which is also what lets it resume where it stopped.