Generate pattern-avoiding permutations

Generate all permutations of the set $\{1,2,\ldots,n\}$ avoiding certain patterns.
Size $n$ of ground set (max. 12)
Forbidden patterns
(max. length 6 for each)
Predefined inputs
Output format
Output  numbering graphics

Object info

Given two permutations $\pi=(a_1,\ldots,a_n)$ and $\tau=(b_1,\ldots,b_k)$, we say that $\pi$ contains the pattern $\tau$, if there is a subsequence $(a_{i_1},a_{i_2},\ldots,a_{i_k})$ of $\pi$, where $i_1\lt i_2\lt \cdots\lt i_k$, whose entries appear in the same relative order as $(b_1,\ldots,b_k)$. An occurrence of such a subsequence is referred to as a match of $\tau$ in $\pi$. Otherwise, we say that $\pi$ avoids the pattern $\tau$. For example, the permutation $\pi=451362$ contains the pattern $\tau=2314$, as witnessed by the subsequence $4516$, which is match of $\tau$ in $\pi$, whereas $\pi$ avoids $\tau'=1234$.

By imposing extra conditions for when a pattern matches, this classical notion of pattern-avoidance can be modified in several ways.

By these definitions, a classical pattern is a mesh pattern with no shaded cells, i.e., all entries of $M$ are 0s. A vincular pattern is a mesh pattern with a single column of shaded cells. A barred pattern is a mesh pattern with a single shaded cell. A boxed pattern is a mesh pattern where all cells in the bounding box of the points of $\tau$ are shaded. For more examples and illustrations of these different types of patterns, see [HHMW20] or one of the aforementioned papers where these patterns were introduced.

The paper [HHMW20] proposes a very general and versatile algorithm, called Algorithm J, for generating many different kinds of pattern-avoiding permutations, which works under some very mild constraints on the patterns. A pattern satisfying these constraints is called tame. Specifically, a classical permutation pattern is tame if the largest entry is not at the boundary. For example, $\tau=231$ is tame, but $\tau'=321$ is not tame. For the conditions when a vincular, barred, boxed or mesh pattern is tame, see [HHMW20]. The algorithm developed in [HHMW20] can generate all pattern-avoiding permutations for any Boolean formula $F$ composed of tame patterns of one of the types discussed before, conjunctions $\wedge$ and disjunctions $\vee$. A conjunction expresses that the permutation must avoid both of the patterns, and a disjunction expresses that the permutation must avoid at least one of the patterns. We write $S_n(F)$ for the set of permutations of length $n$ satisfying the constraints expressed by $F$. For example $S_n(231)$ is the set of permutations avoiding $231$, $S_n(231\wedge 132)$ is the set of permutations avoiding both $231$ and $132$, and $S_n(231\vee 132)$ is the set of permutations avoiding $231$ or $132$. A more complicated set that the algorithm can generate would be $S_n(231\wedge (2\underline{41}3\vee 3\bar{1}42))$.

The implementation of Algorithm J running on this website is due to Chigozie Agomo. The input field takes the formula $F$, with the following grammar rules:
conjunction $\wedge$& (ampersand)
disjunction $\vee$| (vertical bar)
classical pattern $231$231 (consecutive digits)
vincular pattern $2\underline{41}3$24_13 (underscore between the underlined entries)
barred pattern $3\bar{1}42$3b142 (b before overlined entry)
mesh pattern $(231,M)$ with $M$ as above231:0100 0100 1111 0100 (pattern, then colon, followed by matrix $M$ row by row from top to bottom)
precedence constraints231 & (24_13 | 3b142) versus (231 & 24_13) | 3b142 (use parenthesis)

Enumeration (OEIS)

Pattern-avoiding permutations describe and count an abundance of different combinatorial objects, so there is a huge number of OEIS sequences related to them. Some sequences arising from tame patterns that can be generated with this program are listed below.

Download source code

[Zipped C++ source code (GNU GPL)]

References