# Restrictions: subsets in the order they came with Status: **partly built**: the permutation restrictions in induced order, by completion counts; the partition, composition and subset orders. What remains is under "Open". A restriction is a subset of a collection with the order it induces ([[Speculative-Options-Restrictions-and-Orders]] §4). ## 1. The rule A **restriction** keeps its carrier: a derangement is still a `Permutation`, so every permutation statistic and map applies, and nothing is re-declared. `@notatio/structures` holds 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. That table is the specification: filtering the base. A fast collection reproduces it, element by element where the base's order is induced. **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 monotone in rank in the base. **Construction orders become siblings only when they earn it.** A construction order useful in its own right (a Gray code, a generation order an algorithm needs) is a sibling collection with its own name and its order documented, the way `PermutationsAsCycles` is. Otherwise it goes. **Parameterized restrictions are restrictions too.** `KCyclePermutations(n, k)` is `SymmetricGroup(n)` restricted by `CycleCount = k`; `KDescentPermutations` and `KInversionPermutations` likewise. ## 2. Completion counts 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. A restriction without a completion count filters the base, with `cost: enumerative` declared. The completion count is the interface a lex-ordered base offers its restrictions. It is built as a builder for the one base that has restrictions today, shaped so another base can offer the same; it becomes a protocol in [[Structures]] when a second base needs it. Three of the counts, to show the shape: - **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. A completion-count unrank is O(n²) to O(n³) per element, against O(n) to O(n²) for a constructive one, which is fine at the sizes anything enumerates. ## 3. What is built `permutationRestriction` (`packages/symbols/combinatorics/combinatorics/collections/src/families/lex-restriction.ts`) gives unrank, rank, count and membership from a completion count over `prefix`/`filled`, all in Epsil and compiled. Membership defaults to "a full prefix has one completion". The restriction test compares `Restricted(SymmetricGroup(n), …)` with each fast collection element by element. In induced order by completion counts: - `Derangements`, `Involutions`, `CyclicPermutations`, and `KCyclePermutations` (unsigned Stirling numbers of the first kind, of the open paths into the cycles still to close). - `GrassmannianPermutations` and `CograssmannianPermutations` (closed forms), `AlternatingPermutations` (Entringer numbers by first rank), `ConnectedPermutations` (first-cut inclusion–exclusion), `KDescentPermutations` (Eulerian numbers by first entry). - 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 is left is a ballot number (123, 132, 321, 312) or a product of Catalan numbers over the runs of free values (231, 213). - `SeparablePermutations` (Av(2413, 3142)) follows the ⊕/⊖ decomposition over a window of values and the prefix entries still to place; 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, and a closed range is counted by the block of its least value. - `VexillaryPermutations` (Av(2143)): the completion count depends only on a state the prefix leaves, so it is tabulated once per n over every state and cached; unrank and rank are then a few milliseconds. Declared enumerative. Past 2^53 a restriction declines `At` and rank (the count stays exact): its completion count interpreted in exact integers takes minutes there. Each count was checked by brute force over every reachable prefix before it was written in Epsil. Still filtering in `permutation-classes.ts`: `BaxterPermutations` (its count is the closed form), `SimplePermutations` and `SmoothPermutations`. The reference algorithms for Baxter and Smooth are on [[Restriction-Counts]]; Simple has none: the prefixes with distinct futures grow super-exponentially in the free values, so no small state exists. `Subsets` are by size, then lex; `KSubsets` and the restrictions of `Subsets` follow. ## 4. One order per collection, set by its carrier's shape - **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)`; the bitmask order of subsets is `BinaryWords(n)` through `Finset(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 checked puts a direction flag on a collection: Wolfram, Sage, Knuth, FXT, C++ and itertools fix one order and name the others, or reverse the result afterwards. None has rank or unrank honour a direction flag, and reversal is cheap to derive (rank' = count − 1 − rank), so a flag would be ours alone. `IntegerCompositions` is lex on its parts, `IntegerPartitions`' six restrictions follow its order, and `PermutationsAsCycles` stays graded by cycle type (types in reverse lex, lex within a type), since the grading by conjugacy class is the point of the collection. ## Open - The named restriction heads as aliases of `Restricted`, where a catalogue (FindStat, OEIS, Wolfram, Sage) has the name: an alias of the `Restricted` form, not a separate family. - The permutation classes with no completion count: Baxter and Smooth wait on a state a fold can use ([[Restriction-Counts]]), Simple has none known. They filter the base meanwhile. - The same audit of order for restrictions outside permutations, as each is found out: a base says how it is built left to right, and its restrictions count completions of a prefix. The design as first written, with the section numbers that source comments cite, is [[Restrictions Design|Archive-Restrictions-Design]].