Archive Restrictions Design

Restrictions: subsets in the order they came with

Archived. The design as first written, with its original section numbers; adopted since, in whole or in part. Kept for its reasoning; the current page is Restrictions.

Status: decided; first slice built (§5). Follows Speculative Options Restrictions and Orders §4, which defined a restriction as "a subset of a collection with the order it induces", and asks what that commits us to now that the permutation families are Epsil definitions.

1. What we have

A restriction keeps its carrier: a derangement is still a Permutation, so every permutation statistic and map applies, and nothing is re-declared. @enumeratio/structures has the mechanism: Restricted(base, predicate) over a lazy Filter, and a table of named restrictions (RESTRICTIONS: Derangements, CyclicPermutations, DistinctPartitions, the composition restrictions…), each with its predicate as data. A named restriction whose collection has a fast kernel says so (implementedBy), and a test checks the two agree as sets.

As sets, not as sequences. Auditing every family over Permutation against SymmetricGroup's lex order (n = 4, 5, 6):

order	families
induced (lex)	EvenPermutations, KInversionPermutations, BaxterPermutations, BooleanPermutations, NonCrossingPermutations, SeparablePermutations, SimplePermutations, SmoothPermutations, VexillaryPermutations
its own	Derangements, Involutions, CyclicPermutations, AlternatingPermutations, ConnectedPermutations, KCyclePermutations, KDescentPermutations, the six PermutationsAvoiding…, GrassmannianPermutations, CograssmannianPermutations

The split is mechanical: a family that filters SymmetricGroup inherits lex order; a family with a constructive unrank enumerates in its construction's order. Derangements(4) lists 4321, 2341, 3421, 3412, … because its unrank peels off the largest label; Involutions(4) lists 1234, 2134, 3214, 1324, … for the same reason. Those orders were never chosen. They fall out of the algorithm, and nothing records them.

So today "restriction" means two different things depending on which kernel answers, and At(Derangements(4), 2) is not the second derangement of SymmetricGroup(4).

2. Proposal

A restriction head means the induced order. Derangements(n) is Restricted(SymmetricGroup(n), FixedPoints(_x) = 0) in fact, not just in membership: the k-th derangement is the k-th permutation of n in lex order that has no fixed point. Rank in the restriction is then monotone in rank in the base, and "restriction" is one concept.

One mechanism for a fast restriction: count completions. Lex unrank and rank of any restriction of SymmetricGroup work the same way. Choose the entries left to right; at each position, try the values still free in increasing order, and count how many members of the restriction start with the prefix so far. The restriction supplies one thing: that completion count, as an Epsil expression of the prefix. The generic part (choose, count, subtract) is shared. Completion counts for the three families above:

• Derangements. With j entries placed, n − j positions and values left, and m of the free positions whose own label is still free: Σₖ (−1)ᵏ C(m, k) (n − j − k)!.
• Involutions. A position is forced when an earlier entry pointed at it. Otherwise it is fixed (T(f − 1) completions) or paired with a free label above it (T(f − 2) each), where f is the number of free labels.
• Cyclic permutations. The entries so far form disjoint paths. With c of them (counting each unassigned label as a path of one), the completions to a single n-cycle number (c − 1)!, and 0 once a prefix closes a cycle early.

Each is a fold over the prefix with a scalar or small-list state, which compiles on 0.142. A restriction without a completion count falls back to filtering the base, with cost: enumerative declared, which is what the lex-ordered families above already do.

Construction orders become siblings only when they earn it. If a construction order is useful in its own right (a Gray code, a generation order an algorithm needs), it becomes a sibling collection with its own name and its order documented, the way PermutationsAsCycles is. Otherwise it goes. None of the current "own" orders looks like a keeper, but each gets a look before it's dropped.

Parameterised restrictions are restrictions too. KCyclePermutations(n, k) is SymmetricGroup(n) restricted by CycleCount = k; KDescentPermutations and KInversionPermutations likewise. They take the same mechanism, with the parameter free in the predicate and the completion count. A named head stays where a catalogue (FindStat, OEIS, Wolfram, Sage) has the name; it is an alias of the Restricted form, not a separate family.

3. What it costs

• Positions change. Anything that pinned At(Derangements(n), k) and the like: reference examples, Plausible goldens, any page that lists elements. Counts, membership and statistics don't change.
• New unrank/rank definitions for the "own"-ordered families: three are sketched above; the pattern classes and Alternating/Connected need completion counts worked out, or fall back to filtering.
• Speed. A completion-count unrank is O(n²)–O(n³) per element, against the O(n) to O(n²) of today's constructive ones. That's fine at the sizes anything enumerates, and it's measurable with BL-47's method before switching.
• The same question outside permutations. The partition and composition restrictions (DistinctPartitions, OddCompositions, …) need the same audit; the rule is the same.

4. Decisions

The maintainer's answers to the proposal's questions:

1. A restriction head means the induced order. Construction orders become named siblings only if they earn it; otherwise they go.
2. The completion count is the interface a lex-ordered base offers its restrictions. Built first as a builder for the one base that has restrictions today (permutationRestriction), shaped so another base can offer the same; it becomes a protocol in Structures when a second base needs it.
3. Other bases work the same way, found out as they come: a base says how it is built left to right, its restrictions count completions of a prefix.
4. Pattern classes filter until a completion count is known for them (now known for length 3, §5).
5. The Restricted table (@enumeratio/structures, restriction.ts) stays the specification: filtering the base. A fast collection must reproduce it, element by element where the base's order is induced, as sets elsewhere until audited.

5. What is built

• permutationRestriction (collections/src/families/lex-restriction.ts): unrank, rank, count and membership from a completion count over prefix/filled, all in Epsil, all compiled. Membership defaults to "a full prefix has one completion".
• In induced order through it: Derangements, Involutions, CyclicPermutations, and KCyclePermutations (completions are unsigned Stirling numbers of the first kind, of the open paths into the cycles still to close).
• Also by completion counts: GrassmannianPermutations/CograssmannianPermutations (closed: 2^(m − a) or 2^m − m), AlternatingPermutations (Entringer numbers by first rank), ConnectedPermutations (first-cut inclusion–exclusion), KDescentPermutations (Eulerian numbers by first entry). Each formula checked by brute force over every prefix to n = 7.
• The six PermutationsAvoiding… (length-3 patterns): an occurrence with two prefix entries rules out free values in a range; one with a single entry constrains the free values relative to it. What's left is a ballot number (123, 132, 321, 312: the top or bottom k free values in a fixed order) or a product of Catalan numbers over the runs of free values (231, 213). inducedOrder is gone.
• SeparablePermutations (Av(2413, 3142)) follows the ⊕/⊖ decomposition over a window of values and the prefix entries still to place: when the remaining prefix opens with a run on exactly the window's lowest (or highest) values, the shortest such run is the first component; otherwise the first component holds all of the remaining prefix and is a sum of the other kind. O(n⁴) per count, Schröder numbers cached per n.
• NonCrossingPermutations (cycles forming a non-crossing partition): the prefix's edges split 1..n into closed cycles and paths. F(i, j) counts a closed range (no component leaves it) by the block of its least value, each gap and the rest of the range closed in turn; a block of M paths closes into (M − 1)! cycles, a closed cycle is a block on its own. O(n⁴) per count.
• VexillaryPermutations (Av(2143)): its completion count depends only on a state (m, t, S) the prefix leaves (below), so V is tabulated once per n over every state: block m holds 2^m states, t = 0 first and then each t ≥ 1 with its 2^(t − 1) cut sets, S read as a binary number. 2^(n + 1) − 1 entries, cached per n (5.7 s compiled at n = 18); unrank and rank are then a few ms. Declared enumerative, work 9^n (bounds the count and the table).
• All three checked against brute force over every reachable prefix to n = 9 (Vexillary's table layout against that to n = 10) before being written in Epsil, and against the filtering readings element by element to n = 6.
• Still filtering in TS (permutation-classes.ts), with exact counts worked out but not ported (each checked against brute force over every reachable prefix to n = 9):
  • Baxter: read left to right, the new value goes just below a right-to-left minimum or just above a right-to-left maximum (the inverse of the (h, k) generating tree). The sites are two stacks across a cut, each labelled by its gap between prefix values; choosing a site pops everything between it and the cut and pushes a pair. State: the site labels, the cut and the counts left per gap. Measured about n⁵ states (31,147 at n = 24 from a mid start); polynomial unproved, and the state is a list, which a fold can't index.
  • Vexillary (Av(2143), now in Epsil, above): state (m, S, t) over the free values' ranks: ranks above t must come increasing (a prefix inversion), and each cut s ∈ S (a prefix value between ranks s and s + 1, s < t) makes ranks above s increase once a rank ≤ s appears. Integer transitions; about 1.62ⁿ reachable states (35,398 at n = 20), and the minimal automaton is exponential too.
  • Smooth (Av(3412, 4231)): a key of rank thresholds and pairs from the prefix's partial occurrences; about 2.09ⁿ keys (1.4 M at n = 20, 48 s).
  • The code for Baxter and Smooth (and Vexillary's original), with brute-force checkers, is on Restriction Counts.
  • Simple: none found. Prefixes with distinct futures grow super-exponentially in the free values (3, 19, about 170 for m = 2, 3, 4), so no small state exists.
• Past 2^53 a restriction declines At and rank (the count stays exact): its completion count interpreted in exact integers takes minutes there.
• The restriction test compares Restricted(SymmetricGroup(n), …) with each fast collection element by element.

Still to do: the named restriction heads as aliases of Restricted; Baxter and Smooth in Epsil. Smooth's keys aren't a dense range like Vexillary's, so it needs its reachable keys built a layer at a time; Baxter's state is a list. The order audit for the partition and composition restrictions is §6.

6. One order per collection, set by its carrier's shape

The maintainer's rule, from walking through the families (2026-10-01):

• A collection has one order, and its carrier's shape sets it: a word or a list of parts is lex, a nested value is recursive (root split), a cut set or characteristic vector is numeric (bitmask). The order drives rank, unrank and the filtrations a collection can have, so it is not an option on the collection.
• Other orders are other collections, over other carriers, joined by conversions: compositions in their cut words' order are BinaryWords(n − 1) through Composition(word).
• A collection may borrow an order through a bijection when it claims the order isomorphism (orderIsomorphism in the map's record, tested), and with it any compatible filtration. SetPartitions borrows RestrictedGrowthStrings' lex order this way.
• Ascending or descending within the same kind of order is convention, and only flips the leaves within each grade: IntegerPartitions is reverse lex (largest part first), as in Wolfram and Knuth's partition generation. No system we checked puts a direction flag on a collection: Wolfram, Sage (IntegerListsLex, Subsets), Knuth, FXT, C++ and itertools fix one order and name the others (lex vs colex, next_permutation/prev_permutation, Combinatorica's sibling functions), or reverse the result afterwards. The nearest to a parameter are Mathlib's Finset.sort r (the relation itself) and Sage's Permutation.rank(algorithm=…) (a named order). None has rank or unrank honour a direction flag. Reversal is cheap to derive (rank' = count − 1 − rank), so a flag would be ours alone.

Applied so far:

• Compositions: IntegerCompositions is lex on its parts, since its carrier is a list of parts. The bitmask order it had is BinaryWords(n − 1) read through Composition(word), and CutWord no longer claims an order isomorphism. Ten of its eleven restrictions were already lex, so they are now induced as they stand; PalindromicCompositions was reordered to lex.
• Partitions: all six restrictions already follow IntegerPartitions' order.
• Subsets are by size, then lex (Wolfram's order); KSubsets and the restrictions of Subsets follow. The bitmask order is BinaryWords(n) through Finset(word).
• PermutationsAsCycles stays graded by cycle type (types in reverse lex, lex within a type): the grading by conjugacy class is the point of the collection.