Constructing permutations avoiding a pattern

Question

See here for some theory.

It is fairly easy to explicitly generate all permutations of $n$ elements that have a pattern (just begin with the pattern and add the rest in all possible positions), but can I do the same for pattern-avoiding? E.g. consider all permutations that avoid both $[1,2,3]$ and $[3,2,1]$, then the set even for any $n$ is finite, as already for $n=5$ none exists. But it's probably not that easy in general...

Note that I don't care for an enumeration for arbitrarily large $n$ (haaaard, see link) but for an effective algorithm for medium $n$ (say, directly creating $<10^9$ permutations that avoid the pattern[s] for $n=20$, instead of checking $20!$ permutations for validity). A partial result (like "combining pattern foo and bar makes the set empty for large $n$") would be nice too.

Answer 1

As far as "combining pattern foo and bar makes the set empty for large $n$", there is an answer and it is fairly trivial. There are no permutations of length longer than $(k-1)(\ell-1)+1$ that avoid both $12\cdots k$ and $\ell\cdots 21$ by the Erdős–Szekeres theorem. On the other hand, given any set $B$ of patterns, if $B$ does not contain an increasing pattern, then all decreasing permutations will avoid every pattern in $B$. Similarly, if $B$ does not include a decreasing pattern, then all increasing permutations will avoid every pattern in it. Thus there are arbitrarily long $B$-avoiding permutations if and only if $B$ doesn't contain both an increasing pattern and a decreasing pattern.

As for constructing all pattern-avoiding permutations of "reasonable" length, there has been some thought spent on this. Alex points out that there is an approach called "generating trees" that was used in the 90s, both for constructing these permutations and for counting them. The very basic idea is that if you have a list of all pattern-avoiding permutations of length $n-1$, then you can get the pattern-avoiding permutations of length $n$ by inserting $n$ somewhere in those. The less basic version is that you can keep track of which insertions "failed" earlier on, and not try them again. The advanced version is that for certain sets of patterns, there is a pattern to the allowable places for insertions, and this can let you construct those permutations quickly, or even enumerate them without constructing them. But that's only if you get lucky and there is a nice pattern.

Since you asked about constructing the pattern-avoiding permutations, I'll focus on that. PermLab by Michael Albert is a Java program that constructs pattern-avoiding permutations of reasonable length quickly in practice (at least as quickly as a generating tree approach would do, possibly more quickly, and certainly quickly enough for my demands). I'm not sure if Michael has ever written about how it actually does that (maybe he could add a comment if he has?). PermPy by Michael Engen, Cheyne Homberger, and Jay Pantone is a Python library that uses many of the same tricks as PermLab.

All that said, if you want to think more about this, I would recommend starting off with William Kuszmaul's paper "Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations". There are a lot of neat ideas in there and references to other work. One of his ideas that I find very cute, just as a fan of bit-level programming, is that he focuses on permutations of length 16, so that he can represent each one as a single int (on a 64-bit processor), and use various bit operations to manipulate them.