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$
  • 2
    $\begingroup$ What do you mean by "closed by subpatterns"? Is this anything different from avoiding a fixed pattern? $\endgroup$ – Sasho Nikolov Apr 22 '14 at 11:49
  • $\begingroup$ By the reference to Stanley-Wilf, it seems that this is exactly what is intended. $\endgroup$ – Suresh Venkat Apr 22 '14 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$ – Suresh Venkat Apr 22 '14 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 Apr 23 '14 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 Apr 23 '14 at 20:50
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, privacy policy and cookie policy

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