<p>Another approach is enumerative encoding. Consider for example $231$-avoiding permutations, of which there are $C_n$. The number of $231$-avoiding permutations with $\pi^{-1}(n) = i$ is $C_{i-1} C_{n-i}$, and this gives a recursive algorithm for encoding $231$-avoiding permutations: divide the interval $[0,C_n)$ into $n$ intervals $I_1,\ldots,I_n$ of lengths $C_i C_{n-i-1}$ for $i=1,\ldots,n$ arbitrarily. Given a permutation with $\pi^{-1}(n) = i$, notice that $\pi|_{1,\ldots,i-1}$ is a $231$-avoiding permutation of $\{1,\ldots,i-1\}$, and $\pi|_{i+1,\ldots,n}$ is a $231$-avoiding permutation of $\{i+1,\ldots,n\}$. Recursively encode the first part in $[0,C_{i-1})$ and the second part in $[0,C_{n-i})$, and put both encodings together to encode $\pi$ in $I_i$.</p>

<p>For any other $\tau \in S_3$, $\tau$-avoiding permutations are bijectively related to $231$-avoiding permutations, through taking the inverse, complementing the elements, reversing, or the Simion&ndash;Schmidt bijection between $132$- and $123$-avoiding permutations. So this encoding applies to all patterns of length $3$.</p>

CC BY-SA 3.0
2014-04-25T16:10:23.340Z
2014-04-25T16:10:23.340Z
Yuval Filmus
<p>This has been now resolved positively, up to an asymptotically optimal dependence on the pattern. See</p>
<blockquote>
<p>Michal Opler: An Optimal Algorithm for Sorting Pattern-Avoiding Sequences. FOCS 2024: 689-699</p>
</blockquote>
<p>Preprint is available on <a href="https://arxiv.org/abs/2409.07868" rel="nofollow noreferrer">arXiv</a>.</p>

CC BY-SA 4.0
2024-11-01T14:21:28.613Z
2024-11-01T14:21:28.613Z
Michal Opler
<p>For a class $\mathcal{C}$ of permutations, we cannot expect to sort the permutations of $\mathcal{C}$ with less than $O(\log |\mathcal{C}_n|)$ comparisons, where by convention $\mathcal{C}_n := \mathcal{C} \cap S_n$.</p>

<p>In particular, when $\mathcal{C}$ is closed by subpatterns, it follows by Marcus-Tardos theorem (refined by J. Fox) that $|\mathcal{C}_n| \leq C^n$ where $C$ is the <em>Stanley-Wilf constant</em> of $\mathcal{C}$. This leads to the following question: is it possible to sort such a class using at most $O(n \log C)$ comparisons? This question is a strengthening of Question 1 in the paper '<a href="http://epubs.siam.org/doi/pdf/10.1137/1.9781611972979.1">Fast Sorting and Pattern-avoiding Permutations</a>' by D. Arthur.</p>

<p>It seems possible to represent such a sorting strategy by a <em>binary tree</em> which would essentially mimic an 'unbalanced' merge-sort algorithm. Here is the idea: given a permutation $\pi$, we would look for a tree $T_{\pi}$ leaf-labeled by the points of $\pi$, such that for each node $u$ of $T_{\pi}$ the 'overlap' between the two child subtrees would be $O(\log C)$ (either worst-case or on average). However I suspect that a more involved structure is necessary to solve this problem; should it admit a positive solution.</p>

CC BY-SA 3.0
2014-04-22T11:49:32.977Z
What do you mean by "closed by subpatterns"? Is this anything different from avoiding a fixed pattern?
Sasho Nikolov
CC BY-SA 3.0
2014-04-22T20:09:22.327Z
By the reference to Stanley-Wilf, it seems that this is exactly what is intended.
Suresh Venkat
CC BY-SA 3.0
2014-04-22T20:10:11.930Z
A related question: when is it possible to *represent* a class of permutations avoiding a pattern $\beta$ in $n\log C$ bits ?
Suresh Venkat
CC BY-SA 3.0
2014-04-23T20:49:14.977Z
@SashoNikolov: I meant closure under the 'involvement' relation as it is commonly called; this is equivalent to avoiding a (possibly infinite) set of patterns.
NisaiVloot
CC BY-SA 3.0
2014-04-23T20:50:58.967Z
@SureshVenkat: it is feasible for specific classes admitting a tree- or word- based representation; solving the general case with a poly-time representation is open as far as I know. In the language of combinatorial enumeration, this is a *ranking/unranking* problem, while the related *listing* problem can be done efficiently through generating trees.
NisaiVloot
<ds.algorithms><sorting><permutations>
Hierarchical sorting strategies for pattern-avoiding permutations?
NisaiVloot
# Hierarchical sorting strategies for pattern-avoiding permutations?

(Asked by: username_0 on 2014-04-22)

For a class $\mathcal{C}$ of permutations, we cannot expect to sort the permutations of $\mathcal{C}$ with less than $O(\log |\mathcal{C}\_n|)$ comparisons, where by convention $\mathcal{C}\_n := \mathcal{C} \cap S\_n$.

In particular, when $\mathcal{C}$ is closed by subpatterns, it follows by Marcus-Tardos theorem (refined by J. Fox) that $|\mathcal{C}\_n| \leq C^n$ where $C$ is the *Stanley-Wilf constant* of $\mathcal{C}$. This leads to the following question: is it possible to sort such a class using at most $O(n \log C)$ comparisons? This question is a strengthening of Question 1 in the paper '[Fast Sorting and Pattern-avoiding Permutations](http://epubs.siam.org/doi/pdf/10.1137/1.9781611972979.1)' by D. Arthur.

It seems possible to represent such a sorting strategy by a *binary tree* which would essentially mimic an 'unbalanced' merge-sort algorithm. Here is the idea: given a permutation $\pi$, we would look for a tree $T\_{\pi}$ leaf-labeled by the points of $\pi$, such that for each node $u$ of $T\_{\pi}$ the 'overlap' between the two child subtrees would be $O(\log C)$ (either worst-case or on average). However I suspect that a more involved structure is necessary to solve this problem; should it admit a positive solution.

**Tags:** ds.algorithms, sorting, permutations
> **Comments:**
> **username_1**: What do you mean by "closed by subpatterns"? Is this anything different from avoiding a fixed pattern?  
> **username_2**: By the reference to Stanley-Wilf, it seems that this is exactly what is intended.  
> **username_2**: A related question: when is it possible to *represent* a class of permutations avoiding a pattern $\beta$ in $n\log C$ bits ?  
> **username_0**: @SashoNikolov: I meant closure under the 'involvement' relation as it is commonly called; this is equivalent to avoiding a (possibly infinite) set of patterns.  
> **username_0**: @SureshVenkat: it is feasible for specific classes admitting a tree- or word- based representation; solving the general case with a poly-time representation is open as far as I know. In the language of combinatorial enumeration, this is a *ranking/unranking* problem, while the related *listing* problem can be done efficiently through generating trees.  

---

## 2 answers

### Answer by username_3 on 2014-04-25. Score: 2

Another approach is enumerative encoding. Consider for example $231$-avoiding permutations, of which there are $C\_n$. The number of $231$-avoiding permutations with $\pi^{-1}(n) = i$ is $C\_{i-1} C\_{n-i}$, and this gives a recursive algorithm for encoding $231$-avoiding permutations: divide the interval $[0,C\_n)$ into $n$ intervals $I\_1,\ldots,I\_n$ of lengths $C\_i C\_{n-i-1}$ for $i=1,\ldots,n$ arbitrarily. Given a permutation with $\pi^{-1}(n) = i$, notice that $\pi|\_{1,\ldots,i-1}$ is a $231$-avoiding permutation of $\{1,\ldots,i-1\}$, and $\pi|\_{i+1,\ldots,n}$ is a $231$-avoiding permutation of $\{i+1,\ldots,n\}$. Recursively encode the first part in $[0,C\_{i-1})$ and the second part in $[0,C\_{n-i})$, and put both encodings together to encode $\pi$ in $I\_i$.

For any other $\tau \in S\_3$, $\tau$-avoiding permutations are bijectively related to $231$-avoiding permutations, through taking the inverse, complementing the elements, reversing, or the Simion–Schmidt bijection between $132$- and $123$-avoiding permutations. So this encoding applies to all patterns of length $3$.


---

### Answer by username_4 on 2024-11-01. Score: 2

This has been now resolved positively, up to an asymptotically optimal dependence on the pattern. See

> Michal Opler: An Optimal Algorithm for Sorting Pattern-Avoiding Sequences. FOCS 2024: 689-699

Preprint is available on [arXiv](https://arxiv.org/abs/2409.07868).


---

