7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Look up "generating trees". For an early reference on this topic, see e.g. "Generating trees and forbidden subsequences" by Julian West. $\endgroup$ – Alexander Burstein Apr 7 at 16:39
12
$\begingroup$

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, but quickly enough for my demands, certainly). 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.

$\endgroup$
4
  • 2
    $\begingroup$ The approach used in PermLab and in all the other bits of software that I'm aware of focus on generating all the permutations of a given length avoiding a pattern. The problem of course is that this can only work so long as that number is reasonably small. The main question is whether you store all the permutations of length $k$ to generate those of $k+1$ (much quicker in time, but memory-expensive) which is Kuszmaul's approach or use a tree (which with depth-first traversal requires very little memory). $\endgroup$ – Michael Albert Apr 8 at 19:21
  • $\begingroup$ The PermLab link looks broken, Vince. $\endgroup$ – Alexander Burstein Apr 9 at 0:55
  • $\begingroup$ @AlexanderBurstein there is a broken link on that page, but the links under "Files" work for me. $\endgroup$ – Vince Vatter Apr 9 at 9:20
  • $\begingroup$ @VinceVatter I think it’s back now. I guess that was temporary. $\endgroup$ – Alexander Burstein Apr 9 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.