Patterns in permutations
How a permutation contains a pattern, and how Permuta, a Python library for permutations and their patterns, works with them: pattern containment and avoidance, and how it builds a permutation class one length at a time.
Containment and avoidance
Two sequences of distinct numbers are order-isomorphic when their entries are in the same relative order: the smallest entry of one is where the smallest of the other is, the second smallest where the second smallest is, and so on. A permutation \(\sigma\) contains a pattern \(p\) when some subsequence of \(\sigma\) is order-isomorphic to \(p\), and that subsequence is an occurrence of \(p\) in \(\sigma\). Otherwise \(\sigma\) avoids \(p\). In the plot of \(\sigma\) an occurrence of \(p\) is a choice of points that “look like the plot of \(p\).”
How Permuta checks for an occurrence
Give a pattern \(p\) and a permutation \(\sigma\), watch Permuta look for an occurrence of \(p\) in \(\sigma\), or the naive search, which looks at every subsequence, for comparison.
Permuta's Perm.contains asks the pattern for its occurrences in \(\sigma\) (Perm.occurrences_in) and stops at the first. The search places the entries of \(p\) from left to right, each at an entry of \(\sigma\) to the right of the one before, and backs up when an entry cannot be placed.
The clever part is how little it compares. The entries placed so far are already in the order of \(p\), so a new entry is in the right order with all of them once it lies between two: its left floor, the largest entry of \(p\) to its left that is below it, and its left ceiling, the smallest to its left that is above it. Permuta works these out once for each pattern (left_floor_and_ceiling), with how far apart the values must be, so that the entries of \(p\) still to come have room between them (_pattern_details). So each entry of \(\sigma\) it looks at is compared with two numbers, and the search gives up on a branch as soon as fewer entries of \(\sigma\) are left than \(p\) still needs.
The naive search goes through every subsequence of \(\sigma\) with as many entries as \(p\), in the order of their positions, from the first entries of \(\sigma\) to its last. It standardizes each, replacing each entry by its rank among them, smallest first, and checks whether the result equals \(p\). A permutation of length \(n\) has \(\binom{n}{k}\) subsequences of \(k\) entries, each sorted to be standardized, so the naive search does far more work than Permuta's.
A class, one length at a time
A set of permutations is a permutation class if it is closed downwards, in the sense that if \(\sigma\) is in the set, then every pattern that appears in \(\sigma\), is also in the set. \(\operatorname{Av}(B)\), the set of all permutations that avoid all the patterns in \(B\), forms a permutation class, and \(B\) is called its basis. Every permutation class can be given as \(\operatorname{Av}(B)\) for some \(B\). Removing the last entry of a member leaves a member one shorter, so each member of length \(n + 1\) is a member of length \(n\) with a new last entry. Permuta's Av builds the class this way, a length at a time: a member of length \(n\) has \(n + 1\) heights for a new last entry, below all its entries, between two of them or above all, and each new permutation is kept unless it contains a pattern of \(B\).
The clever part is that Permuta never looks for a pattern while it does this. It keeps each member's spots, the heights where a new last entry makes a member. A pattern of \(B\) that a new last entry creates uses the new entry and at most \(m - 1\) others, where \(m\) is the length of the longest pattern in \(B\), so it leaves out one of the member's last \(m\) entries. The member without that entry, one shorter, then lacks the height among its spots. So a member's spots are the heights that each member without one of its last \(m\) entries allows. All that is left to check is whether a new permutation is itself a pattern of \(B\).
Containment and avoidance
A mesh pattern is a pattern \(p\) with some of the boxes of its plot shaded. The lines through the points of the plot of a pattern of length \(k\) cut it into \((k + 1)^2\) boxes, and \((i, j)\) is the box right of its first \(i\) entries and above its \(j\) smallest, counted from \((0, 0)\) at the bottom left. An occurrence of a mesh pattern in \(\sigma\) is an occurrence of \(p\) such that no entry of \(\sigma\) lies in a shaded box: the lines through the points of the occurrence cut the plot of \(\sigma\) into the same boxes, and those that are shaded in the pattern must be empty. Otherwise \(\sigma\) avoids the mesh pattern. A classical pattern is a mesh pattern with no box shaded.
How Permuta checks for an occurrence
Give a pattern \(p\), the boxes to shade and a permutation \(\sigma\), or shade a box by clicking it in the picture of the pattern, and watch Permuta look for an occurrence of the mesh pattern in \(\sigma\), or the naive search, for comparison.
Permuta's MeshPatt.occurrences_in asks the pattern \(p\) for its occurrences in \(\sigma\), with the search of the classical patterns' tab, and checks each one as the search finds it. It goes through \(\sigma\) from left to right, counting the entries of the occurrence it goes past, and finds the box of each other entry: the number of the occurrence's entries to its left, and the number below it. At the first entry in a shaded box it drops the occurrence, and the search for \(p\) goes on. An occurrence with no entry in a shaded box is an occurrence of the mesh pattern, and Perm.contains stops there.
The naive search goes through every subsequence of \(\sigma\) with as many entries as \(p\), standardizes each, and where the result equals \(p\), looks at every other entry of \(\sigma\) for one in a shaded box.
A set, one length at a time
The permutations that avoid every pattern of a set \(M\) of mesh patterns, \(\operatorname{Av}(M)\), need not form a permutation class: a pattern of a member need not be a member, since an entry that lay in a shaded box may be gone. So Permuta cannot make each length from the one before, as it does for a basis of classical patterns. For a basis of mesh patterns, its Av goes through every permutation of each length, in lexicographic order, and keeps those that avoid every pattern of \(M\), looking for each pattern with the search above.