Stack-sortable permutation - Stack-sortable permutation

Yilda matematika va Kompyuter fanlari, a stack-sortable permutation (shuningdek, a daraxtlarni almashtirish)^[1] a almashtirish kimning elementlari bo'lishi mumkin saralangan ichki xotirasi bitta bilan cheklangan algoritm bo'yicha stack ma'lumotlar tuzilishi. Stack-sortable permutations - bu o'z ichiga olmaydi almashtirish tartibi 231; ular tomonidan hisoblanadi Kataloniya raqamlari va joylashtirilishi mumkin bijection bir xil hisoblash funktsiyasiga ega bo'lgan ko'plab boshqa kombinatorial ob'ektlar bilan Dik yo'llari va ikkilik daraxtlar.

Yig'ma bilan saralash

Stek yordamida kirish ketma-ketligini saralash muammosi birinchi bo'lib paydo bo'lgan Knut (1968), kim quyidagilarni berdi chiziqli vaqt algoritm (keyingi algoritmlar bilan chambarchas bog'liq) barcha yaqinroq kichik qiymatlar muammo):

Bo'sh to'plamni boshlang
Har bir kirish qiymati uchun x:
- Stack bo'sh emas va x stek ustki qismidan kattaroq bo'lsa, stekni chiqishga qo'ying
- Durang x suyakka
Stek bo'sh bo'lmasa-da, uni chiqishga qo'ying

Knut ushbu algoritm ba'zi bir kirish ketma-ketliklarini to'g'ri saralashini, boshqalarini esa tartiblashda muvaffaqiyatsizlikka uchraganligini kuzatdi. Masalan, 3,2,1 ketma-ketligi to'g'ri tartiblangan: uchta element hammasi stakka surilib, so'ngra 1,2,3 tartibida joylashtirilgan. Biroq, 2,3,1 ketma-ketligi to'g'ri tartiblanmagan: algoritm avval 2 ni itaradi va kattaroq kirish qiymatini 3 ko'rganda uni ochadi, natijada 2 undan keyin emas, balki 1dan oldin chiqadi.

Chunki bu algoritm a taqqoslash, uning muvaffaqiyati yoki muvaffaqiyatsizligi kirish ketma-ketligining son qiymatlariga bog'liq emas, balki ularning nisbiy tartibiga bog'liq; ya'ni kirish bilan tavsiflanishi mumkin almashtirish ushbu kirishni bir xil uzunlikdagi tartiblangan ketma-ketlikdan hosil qilish uchun kerak edi. Knut ushbu algoritm to'g'ri ajratilgan almashtirishlarni aniq o'z ichiga olmagan almashtirishlar sifatida tavsifladi almashtirish tartibi 231: uchta element x, yva z, kirishda shu tartibda paydo bo'ladi, bilan z < x < y. Bundan tashqari, agar u algoritm kiritishni tartiblay olmasa, u holda bu kirishni bitta to'plam bilan saralash mumkin emasligini kuzatdi.

Bundan tashqari, murakkab stack tizimlari va tegishli ma'lumotlar tuzilmalari yordamida saralash bo'yicha keyingi ishlarga ilhom berish bilan bir qatorda,^[2] Knutning tadqiqotlari o'rganishni boshladi almashtirish naqshlari va taqiqlangan naqshlar bilan belgilangan almashtirish sinflari.

Bijections va sanab chiqish

Knutning saralash algoritmi tomonidan bajariladigan turtki va poplar ketma-ketligi, u stek-sortable permutation for a sort Dyk tili: surishni chap qavs sifatida, popni o'ng qavs sifatida qayta talqin qilish muvozanatli qavs qatorini hosil qiladi. Bundan tashqari, har bir Dyck mag'lubiyati shu tarzda stack-sortable permutation-dan kelib chiqadi va har ikki stack-sortable permutations-dan farqli o'laroq Dyck torlari hosil bo'ladi. Shu sababli, uzunlikdagi stack-sortable permutations soni n uzunlikdagi Dyck torlari soni bilan bir xiln, Kataloniya raqami

{ displaystyle C_ {n} = { frac {1} {n + 1}} { binom {2n} {n}}.}

^[3]

Orasidagi biektsiya ikkilik daraxtlar (tugunlar chapdan o'ngga raqamlangan) va stack-sortable permutations, bir xil tugun raqamlarini oldindan buyurtma

Stack-sortable permutations shuningdek to'g'ridan-to'g'ri va (yorliqsiz) tarjima qilinishi mumkin ikkilik daraxtlar, boshqa kombinatoriya sinfi kimning hisoblash funktsiyasi - katalan raqamlarining ketma-ketligi. Ikkilik daraxt o'z tugunlarini raqamlash orqali stack-sortable permutation-ga aylantirilishi mumkin chapdan o'ngga buyurtma va keyin ushbu raqamlarni a tashrif buyuradigan tartibda yozing oldindan buyurtma daraxtning: avval ildiz, so'ng chap chap daraxt, keyin o'ng pastki daraxt, davom etmoqda rekursiv har bir kichik daraxt ichida. Orqaga yo'nalishda, stack-sortable permutation birinchi qiymat bo'lgan daraxtga dekodlanishi mumkin x almashtirishning keyingi qismi daraxtning ildiziga to'g'ri keladi x - Ildizning chap bolasini berish uchun 1 qiymat rekursiv ravishda dekodlanadi, qolgan qiymat esa to'g'ri bolani berish uchun yana rekursiv ravishda dekodlanadi.^[1]

Bir nechta boshqa almashtirish sinflari, shuningdek, stack-sortable permutations bilan bijectionga joylashtirilishi mumkin. Masalan, 132, 213 va 312 naqshlaridan qochadigan permutatsiyalar har bir qiymatni almashtirib, almashtirishni teskari yo'naltirish yo'li bilan stack-sortable (231-oldini olish) permutations dan hosil bo'lishi mumkin. x tomonidan almashtirishda n + 1 − xyoki ikkala operatsiya ham birlashtirilgan. 312-dan qochadigan almashtirishlar, shuningdek, 231-dan qochadigan almashtirishlarning teskari tomonlari va ular deb nomlangan ketma-ket amalga oshiriladigan almashtirishlar chunki ular identifikatorning o'rnini bosish natijasida stakka kiritish va ochish-chiqish operatsiyalari ketma-ketligi bilan hosil bo'lishi mumkin bo'lgan almashtirishlardir.^[4]Sifatida Knut (1968) 123-dan qochish va 321-dan qochish bilan almashtirishlar, stack-sortable permutations bilan bevosita bog'liq bo'lmaganiga qaramay, bir xil hisoblash funktsiyasiga ega.

Tasodifiy stack-sortable permutations

Rotem (1981) tanlangan stack-sortable permutations xususiyatlarini o'rganadi bir xil tasodifiy berilgan uzunlikdagi barcha bunday almashtirishlar orasida kutilgan uzunlik ning eng uzun tushadigan ketma-ketlik bunday almashtirishda ${ displaystyle { sqrt { pi n}} - O (1)}$ , cheklanmagan tasodifiy almashtirishlardan doimiy koeffitsient bilan farq qiladi (ular uchun kutilgan uzunlik taxminan bo'ladi ${ displaystyle 2 { sqrt {n}}}$ ). Eng uzun ko'tarilish ketma-ketligining kutilgan uzunligi cheklanmagan almashtirishlardan yanada kuchli farq qiladi: bu shunday ${ displaystyle (n + 1) / 2}$ . O'tkazish ichidagi barcha oldingi qiymatlardan kattaroq qiymatlarning kutilgan soni faqat ${ displaystyle 3-6 / (n + 2)}$ , cheklanmagan almashtirishlar uchun uning logaritmik qiymatidan kichikroq. Va kutilgan soni inversiyalar bu ${ displaystyle Theta (n ^ {3/2})}$ , ning qiymatidan farqli o'laroq ${ displaystyle Theta (n ^ {2})}$ cheklanmagan almashtirishlar uchun.

Qo'shimcha xususiyatlar

Har qanday almashtirish a ni belgilaydi almashtirish grafigi, tepaliklari almashtirish elementlari bo'lgan va qirralari bo'lgan juft elementlarni birlashtirgan grafik teskari almashtirish orqali. Stack-sortable permutations ning almashtirish grafikalari ahamiyatsiz mukammal.^[4]

Har bir element uchun men almashtirish p, aniqlang b_men chap tomonda joylashgan va undan katta bo'lgan boshqa elementlarning soni bo'lishi men. Keyin p barcha uchun va agar shunday bo'lsa, stack-sortable men, b_men − b_men + 1 ≤ 1.^[1]

Algoritmlar

Knott (1977) stack-sortable permutations va binar daraxtlar orasidagi bijectiondan foydalanib, har bir binar daraxt uchun raqamli darajani belgilaydi va daraxt darajasini hisoblash uchun samarali algoritmlarni ("martabali") va daraxtni berilgan daraja bilan hisoblash uchun ("unranking") ").

Mishel va Rossin (2006) almashtirishlar bo'yicha ikkita tahrirlash operatsiyasini aniqladi: o'chirish (tuzish a almashtirish tartibi ) va unga teskari. Daraxtlar va almashtirishlar orasidagi bir xil yozishmalardan foydalanib, ular ushbu operatsiyalarga mos kelishini kuzatdilar chekka qisqarish daraxtda va uning teskari tomonida. Qo'llash orqali polinom vaqti dinamik dasturlash uchun algoritm masofani tahrirlash daraxtlarda ular stack-sortable permutations (va shuning uchun ham eng uzun umumiy naqsh) orasidagi tahrir masofasini polinom vaqtida topish mumkinligini ko'rsatdilar. Keyinchalik ushbu uslub eng uzun tarqalgan naqshlarni topish algoritmlarida umumlashtirildi ajratiladigan almashtirishlar;^[5] ammo, eng uzun tarqalgan naqsh muammosi o'zboshimchalik bilan almashtirish uchun NP-ni to'ldiradi.^[6]

Izohlar

^ ^a ^b ^v Knott (1977).
^ Tarjan (1972); Avis va Yangi tug'ilgan (1981); Rozenstiehl va Tarjan (1984); Bona (2002); Felsner va Pergel (2008). Bona tomonidan berilgan ko'plab qo'shimcha ma'lumotlarga qarang.
^ Knut (1968); Rotem (1981).
^ ^a ^b Rotem (1981).
^ Bouvel, Rossin va Vialette (2007).
^ Mishel va Rossin (2006).

Adabiyotlar

Avis, Devid; Yangi tug'ilgan chaqaloq, Monro (1981), "Seriyadagi pop-staklarda", Utilitas Mathematica, 19: 129–140, JANOB 0624050.
Bona, Miklos (2002), "Stack-sorting intizomlari bo'yicha so'rovnoma", Elektron kombinatorika jurnali, 9 (2): A1, JANOB 2028290.
Bouvel, Matilde; Rossin, Dominik; Vialette, Stéphane (2007), "Permutasiyalar orasida eng uzun tarqalgan ajratiladigan naqsh", Kombinatorial naqshlarni taqqoslash (CPM 2007), Kompyuter fanidan ma'ruza matnlari, 4580, Springer, 316–327 betlar, doi:10.1007/978-3-540-73437-6_32.
Felsner, Stefan; Pergel, Martin (2008), "Stak va navbatlar tarmoqlari bilan saralashning murakkabligi", Proc. 16-ev. Simp. Algoritmlar, Karlsrue, Germaniya, 417-429 betlar, doi:10.1007/978-3-540-87744-8_35, ISBN 978-3-540-87743-1.
Knott, Gari D. (1977 yil fevral), "Ikkilik daraxtlar uchun raqamlash tizimi", ACM aloqalari, 20 (2): 113–115, doi:10.1145/359423.359434.
Knuth, Donald (1968), "1-jild: Asosiy algoritmlar", Kompyuter dasturlash san'ati, Reading, Mass.: Addison-Uesli.
Micheli, Anne; Rossin, Dominik (2006), "Belgilanmagan buyurtma qilingan daraxtlar orasidagi masofani tahrirlash", Nazariy informatika va ilovalar, 40 (4): 593–609, arXiv:matematik / 0506538, doi:10.1051 / ita: 2006043, JANOB 2277052.
Rozenstixl, Per; Tarjan, Robert E. (1984), "Gauss kodlari, planlangan Gemilton grafikalari va stack-sortable permutations", Algoritmlar jurnali, 5 (3): 375–390, doi:10.1016 / 0196-6774 (84) 90018-X, JANOB 0756164
Rotem, D. (1981), "Stack sortable permutations", Diskret matematika, 33 (2): 185–196, doi:10.1016 / 0012-365X (81) 90165-5, JANOB 0599081.
Tarjan, Robert (1972 yil aprel), "Navbat va stak tarmoqlaridan foydalanib saralash", ACM jurnali, 19 (2): 341–346, doi:10.1145/321694.321704.

[knott-1] v Knott (1977).

[2] Tarjan (1972); Avis va Yangi tug'ilgan (1981); Rozenstiehl va Tarjan (1984); Bona (2002); Felsner va Pergel (2008). Bona tomonidan berilgan ko'plab qo'shimcha ma'lumotlarga qarang.

[3] Knut (1968); Rotem (1981).

[rotem81-4] Rotem (1981).

[5] Bouvel, Rossin va Vialette (2007).

[6] Mishel va Rossin (2006).

[1]

[2]

[3]

[4]

[5]

[6]