Restrictions

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. @enumeratio/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.