Strategi penyortiran hierarkis untuk permutasi yang menghindari pola?

Untuk kelas permutasi, kita tidak bisa berharap untuk mengurutkan permutasi C dengan kurang dari O ( log | C n | ) perbandingan, di mana dengan konvensi C n : = C ∩ S n .$\mathcal{C}$$\mathcal{C}$$O(\log |\mathcal{C}_n|)$$\mathcal{C}_n := \mathcal{C} \cap S_n$

Khususnya, ketika ditutup oleh subpatterns, itu diikuti oleh teorema Marcus-Tardos (disempurnakan oleh J. Fox) yang | C n | ≤ C n di mana C adalah konstanta Stanley-Wilf dari C . Ini mengarah pada pertanyaan berikut: apakah mungkin untuk mengurutkan kelas seperti itu menggunakan paling banyak perbandingan O ( n log C ) ? Pertanyaan ini adalah penguatan dari Pertanyaan 1 di makalah ' Permutasi Cepat Penyortiran dan Penghindaran Pola ' oleh D. Arthur.$\mathcal{C}$$|\mathcal{C}_n| \leq C^n$$C$$\mathcal{C}$$O(n \log C)$

Tampaknya mungkin untuk merepresentasikan strategi penyortiran seperti itu oleh pohon biner yang pada dasarnya akan meniru suatu algoritma merge-sort yang 'tidak seimbang'. Berikut adalah ide: diberikan permutasi , kita akan mencari pohon T π daun-berlabel dengan poin dari π , sehingga untuk setiap node u dari T π yang 'tumpang tindih' antara dua sub pohon anak akan menjadi O ( log C ) (baik yang terburuk atau rata-rata). Namun saya menduga bahwa struktur yang lebih terlibat diperlukan untuk menyelesaikan masalah ini; haruskah itu mengakui solusi positif.$\pi$$T_{\pi}$$\pi$$u$$T_{\pi}$$O(\log C)$

Pendekatan lain adalah pengkodean enumeratif. Pertimbangkan misalnya -hindari permutasi, yang ada C n . Jumlah 231 -menghapus permutasi dengan π - 1 ( n ) = i adalah C i - 1 C n - i , dan ini memberikan algoritma rekursif untuk pengkodean 231 -menghindari permutasi: bagi interval [ 0 , C n ) menjadi n interval I 1 , ... $231$$C_n$$231$$\pi^{-1}(n) = i$$C_{i-1} C_{n-i}$$231$$[0,C_n)$$n$ panjang C i C n - i - 1 untuk i = 1 , … , n sewenang-wenang. Diberi permutasi dengan π - 1 ( n ) = i , perhatikan bahwa π | 1 , … , i - 1 adalah 231 permutasi dari { 1 , … , i - 1 } , dan π | $I_1,\ldots,I_n$$C_i C_{n-i-1}$$i=1,\ldots,n$$\pi^{-1}(n) = i$$\pi|_{1,\ldots,i-1}$$231$$\{1,\ldots,i-1\}$ adalahpermutasi231-hindari{i+1,...,n}. Secara encode rekam bagian pertama dalam[0, C i - 1 )dan bagian kedua dalam[0, C n - i ), dan satukan kedua penyandian untuk menyandikanπdi I i .$\pi|_{i+1,\ldots,n}$$231$$\{i+1,\ldots,n\}$$[0,C_{i-1})$$[0,C_{n-i})$$\pi$$I_i$

Untuk setiap , τ permutasi yang tidak berhubungan secara bijektif berkaitan dengan 231- permutasi yang tidak berlaku, melalui pengambilan invers, melengkapi elemen, membalikkan, atau pengawetan Simion-Schmidt antara 132 - dan 123 permutasi yang tidak berlaku. Jadi pengkodean ini berlaku untuk semua pola dengan panjang 3 .$\tau \in S_3$$\tau$$231$$132$$123$$3$