8
$\begingroup$

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' 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.

$\endgroup$
5
  • 2
    $\begingroup$ What do you mean by "closed by subpatterns"? Is this anything different from avoiding a fixed pattern? $\endgroup$ Commented Apr 22, 2014 at 11:49
  • $\begingroup$ By the reference to Stanley-Wilf, it seems that this is exactly what is intended. $\endgroup$ Commented Apr 22, 2014 at 20:09
  • 1
    $\begingroup$ A related question: when is it possible to represent a class of permutations avoiding a pattern $\beta$ in $n\log C$ bits ? $\endgroup$ Commented Apr 22, 2014 at 20:10
  • 1
    $\begingroup$ @SashoNikolov: I meant closure under the 'involvement' relation as it is commonly called; this is equivalent to avoiding a (possibly infinite) set of patterns. $\endgroup$
    – NisaiVloot
    Commented Apr 23, 2014 at 20:49
  • $\begingroup$ @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. $\endgroup$
    – NisaiVloot
    Commented Apr 23, 2014 at 20:50

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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