Стек-сұрыпталатын ауыстыру - Stack-sortable permutation

Жылы математика және Информатика, а стек-сұрыпталатын ауыстыру (а деп те аталады ағаштарды ауыстыру)^[1] Бұл ауыстыру элементтері болуы мүмкін сұрыпталған алгоритм бойынша, оның ішкі жады бірімен шектеледі стек деректер құрылымы. Стек-сұрыпталатын ауыстырулар - бұл дәл құрамындағы пермутациялар ауыстыру үлгісі 231; оларды санайды Каталон нөмірлері, және орналастырылуы мүмкін биекция санақ функциясы бар көптеген басқа комбинаторлық объектілермен бірге Дайк жолдары және екілік ағаштар.

Стекпен сұрыптау

Стек көмегімен енгізу ретін сұрыптау мәселесі бірінші болып туындады Кнут (1968), кім берді сызықтық уақыт алгоритм (кейінгі алгоритмдермен тығыз байланысты барлық жақын мәндер проблема):

Бос стекті инициализациялаңыз
Әрбір енгізу мәні үшін х:
- Стек бос емес және х стектегі үстіңгі элементтен үлкенірек, стекті шығысқа шығарыңыз
- Басыңыз х стекке
Стек бос болмаса да, оны нәтижеге шығарыңыз

Кнут бұл алгоритм кейбір енгізу реттілігін дұрыс сұрыптайтынын, ал басқаларын сұрыптай алмайтынын байқады. Мысалы, 3,2,1 реттілігі дұрыс сұрыпталған: үш элемент барлығы стекке итеріліп, содан кейін 1,2,3 ретімен орналастырылған. Алайда, 2,3,1 реттілігі дұрыс сұрыпталмаған: алгоритм алдымен 2-ді итеріп, 3-тің үлкен мәнін көргенде оны шығарады, содан кейін 2 емес, 1-ден бұрын шығады.

Себебі бұл алгоритм а салыстыру, оның жетістігі немесе сәтсіздігі кіріс тізбегінің сандық мәндеріне байланысты емес, тек олардың салыстырмалы тәртібіне байланысты; яғни кіріс арқылы сипатталуы мүмкін ауыстыру сол кірісті бірдей ұзындықтағы сұрыпталған тізбектен қалыптастыру үшін қажет. Кнут осы алгоритмнің дұрыс сұрыптайтын ауыстыруларды дәл құрамында жоқ пермутациялар ретінде сипаттады ауыстыру үлгісі 231: үш элемент х, ж, және з, кірісте сол ретпен пайда болады, бірге з < х < ж. Оның үстіне, егер алгоритм кірісті сұрыптай алмаса, онда бұл кірісті бір стекпен сұрыптауға болмайтынын байқады.

Сондай-ақ, стектердің және олармен байланысты құрылымдардың күрделі жүйелерін пайдалану арқылы сұрыптау бойынша көптеген кейінгі жұмыстарды шабыттандырумен қатар,^[2] Кнуттың зерттеулері зерттеуді бастады ауыстыру үлгілері және тыйым салынған үлгілермен анықталған ауыстыру сыныптары.

Бағдарлау және санау

Кнуттың сұрыптау алгоритмі бойынша орындалатын итеру мен поптардың реттілігі, ол стек бойынша сұрыпталатын ауыстыру формасын сұрыптайды Дик тілі: итеруді сол жақ жақша ретінде, ал попты оң жақша ретінде қайта түсіндіру теңдестірілген жақшалар тізбегін шығарады. Сонымен қатар, Dyck-тің кез-келген жолы стек-сұрыпталатын ауыстыру тәсілінен шығады және әр екі стек-сұрыпталатын ауыстырудың әрқайсысы Dyck-тің жолдарын шығарады. Осы себептен стек-сұрыпталатын ұзындықтың ауыстыру саны n ұзындығы 2 болатын Дик жіптерінің санымен бірдейn, Каталон нөмірі

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

^[3]

Арасындағы байланыс екілік ағаштар (солдан оңға қарай нөмірленген түйіндермен) және стек бойынша сұрыпталатын ауыстырулар, сол түйін нөмірлерін тізімге енгізу арқылы жасалған алдын ала берілетін тапсырыс

Стек-сұрыпталатын ауыстырулар тікелей және (белгілері жоқ) тілден аударылуы мүмкін екілік ағаштар, басқа комбинаторлық сынып кімдікі санау функциясы - каталон сандарының кезектілігі. Екілік ағаш түйіндерді нөмірлеу арқылы стек-сұрыпталатын ауыстыруға айналуы мүмкін солдан оңға қарай тапсырыс беру, содан кейін осы сандарды а баратын ретпен тізімдеңіз алдын-ала өту ағаштың: алдымен тамыр, содан кейін сол жақ ағаш, содан кейін оң жақ ағаш рекурсивті әр кіші ағаш ішінде. Кері бағытта стек-сұрыпталатын ауыстыру бірінші мән болатын ағашқа декодталуы мүмкін х ауыстыру ағаштың тамырына сәйкес келеді, келесі х - түбірдің сол жақ баласын беру үшін 1 мән рекурсивті түрде декодталады, ал қалған мәндер дұрыс баланы беру үшін қайтадан рекурсивті түрде декодталады.^[1]

Бірнеше басқа ауыстыру кластарын стек-сұрыпталатын ауыстырулармен биекцияға орналастыруға болады. Мысалы, 132, 213 және 312 заңдылықтарын болдырмайтын ауыстырулар, стек-сұрыпталатын (231 болдырмайтын) ауыстырулардан, әр ауыстыруды ауыстырып, ауыстыруды өзгерту арқылы құрылуы мүмкін. х арқылы ауыстыруда n + 1 − хнемесе екі амал да біріктірілген. 312 болдырмайтын ауыстырулар сонымен қатар 231 болдырмайтын ауыстырудың кері шамалары болып табылады және оларды «деп атайды стек арқылы жүзеге асырылатын ауыстырулар өйткені олар идентификациялық пермутациядан стекке кірістен итеріп шығару және шығарудан шығаруға арналған операциялар тізбегі арқылы құрылуы мүмкін ауыстырулар болып табылады.^[4]Қалай Кнут (1968) 123 болдырмайтын және 321 болдырмайтын алмастырулар стекпен сұрыпталатын ауыстырулармен тікелей байланыссыз болғанымен, бірдей есептеу функциясына ие екенін атап өтті.

Кездейсоқ стекпен сұрыпталатын ауыстырулар

Ротем (1981) таңдалған стек-сұрыпталатын ауыстырудың қасиеттерін зерттейді біркелкі кездейсоқ Берілген ұзындықтағы барлық осындай ауыстырулардың арасында күтілетін ұзындық туралы ең төмен түсетін субвенция мұндай ауыстыруда ${ displaystyle { sqrt { pi n}} - O (1)}$ , шектеусіз кездейсоқ ауыстырулардан тұрақты фактормен ерекшеленеді (олар үшін күтілетін ұзындық шамамен болады) ${ displaystyle 2 { sqrt {n}}}$ ). Ең ұзын көтерілу кезегінің күтілетін ұзындығы шектеусіз ауыстырулардан анағұрлым қатты ерекшеленеді: бұл ${ displaystyle (n + 1) / 2}$ . Барлық алдыңғы мәндерден үлкен болатын ауыстырудың ішіндегі күтілетін мәндер саны ғана ${ displaystyle 3-6 / (n + 2)}$ , шектеусіз ауыстырулар үшін логарифмдік мәнінен кіші. Және күтілетін саны инверсия болып табылады ${ displaystyle Theta (n ^ {3/2})}$ , оның мәнінен айырмашылығы ${ displaystyle Theta (n ^ {2})}$ шектеусіз ауыстырулар үшін.

Қосымша қасиеттер

Әрбір ауыстыру а анықтайды ауыстыру графигі, шыңдары ауыстырудың элементтері болып табылатын және шеттері болып табылатын жұп элементтерін қосатын график төңкерілген ауыстыру арқылы. Стек-сұрыпталатын ауыстырудың ауыстыру графиктері болып табылады маңызды емес.^[4]

Әрбір элемент үшін мен ауыстыру туралы б, анықтаңыз б_мен сол жақта және одан үлкен элементтердің саны болуы керек мен. Содан кейін б стек-сұрыптауға болады, егер ол болса, бәрі үшін мен, б_мен − б_мен + 1 ≤ 1.^[1]

Алгоритмдер

Нотт (1977) әр екілік ағаш үшін сандық дәрежені анықтау үшін және ағаштың дәрежесін есептеу үшін тиімді алгоритмдерді құру үшін («дәрежелеу») және берілген дәрежемен ағашты есептеу үшін «» тізбектелген ауыстыру және екілік ағаштар арасындағы биекцияны қолданады «).

Мишели және Россин (2006) ауыстыру бойынша екі өңдеу әрекетін анықтады: жою (а жасау ауыстыру үлгісі ) және оған кері. Ағаштар мен алмастырулар арасындағы бірдей сәйкестікті қолдана отырып, олар бұл амалдардың сәйкес келетіндігін байқады жиектің жиырылуы ағашта және оның кері жағы. Қолдану арқылы көпмүшелік уақыт динамикалық бағдарламалау үшін алгоритм қашықтықты өңдеу ағаштарда олар стек-сұрыпталатын екі ауыстырудың арасындағы түзету қашықтығын (және, демек, ең ұзын ортақ өрнек) көпмүшелік уақытта табуға болатындығын көрсетті. Кейіннен бұл әдіс ең ұзын үлгілерді табудың алгоритмдерінде жинақталды бөлінетін ауыстырулар;^[5] дегенмен, ересек ауыстырулар үшін NP-аяқталған ең көп кездесетін үлгі проблемасы.^[6]

Ескертулер

^ ^а ^б ^c Нотт (1977).
^ Таржан (1972); Avis & Newborn (1981); Розенстиль және Таржан (1984); Бон (2002); Felsner & Pergel (2008). Бонаның қосымша сілтемелерін де қараңыз.
^ Кнут (1968); Ротем (1981).
^ ^а ^б Ротем (1981).
^ Bouvel, Rossin & Vialette (2007).
^ Мишели және Россин (2006).

Әдебиеттер тізімі

Авис, Дэвид; Жаңа туылған бала, Монро (1981), «Поп-стектерде», Utilitas Mathematica, 19: 129–140, МЫРЗА 0624050.
Бона, Миклос (2002), «Стек-сұрыптау пәндеріне сауалнама», Комбинаториканың электронды журналы, 9 (2): A1, МЫРЗА 2028290.
Бувель, Матильда; Россин, Доминик; Vialette, Stéphane (2007), «Пермутаттар арасындағы ең ұзын бөлінетін үлгі», Үлгілерді үйлестіруді үйлестіру (CPM 2007), Информатикадағы дәрістер, 4580, Springer, 316–327 б., дои:10.1007/978-3-540-73437-6_32.
Фельснер, Стефан; Пергел, Мартин (2008), «Дестелер мен кезектер желілерімен сұрыптаудың күрделілігі», Proc. 16-шы еур. Симптом. Алгоритмдер, Карлсруэ, Германия, 417–429 бет, дои:10.1007/978-3-540-87744-8_35, ISBN 978-3-540-87743-1.
Нотт, Гари Д. (1977 ж. Ақпан), «Екілік ағаштарға арналған нөмірлеу жүйесі», ACM байланысы, 20 (2): 113–115, дои:10.1145/359423.359434.
Кнут, Дональд (1968), «1-том: Іргелі алгоритмдер», Компьютерлік бағдарламалау өнері, Рединг, Массачусетс: Аддисон-Уэсли.
Мишели, Анна; Россин, Доминик (2006), «Жапсырмасыз тапсырыс берілген ағаштар арасындағы қашықтықты өзгерту», Теориялық информатика және қолдану, 40 (4): 593–609, arXiv:математика / 0506538, дои:10.1051 / ita: 2006043, МЫРЗА 2277052.
Розенстиль, Пьер; Тарджан, Роберт Е. (1984), «Гаусс кодтары, жазықтықтағы Гамильтон графиктері және стек-сұрыпталатын ауыстырулар», Алгоритмдер журналы, 5 (3): 375–390, дои:10.1016 / 0196-6774 (84) 90018-X, МЫРЗА 0756164
Rotem, D. (1981), «Stack sortable permutations», Дискретті математика, 33 (2): 185–196, дои:10.1016 / 0012-365X (81) 90165-5, МЫРЗА 0599081.
Тарджан, Роберт (1972 ж. Сәуір), «Кезектер мен стектердің желілерін пайдалану арқылы сұрыптау», ACM журналы, 19 (2): 341–346, дои:10.1145/321694.321704.

[knott-1] а ^б ^c Нотт (1977).

[2] Таржан (1972); Avis & Newborn (1981); Розенстиль және Таржан (1984); Бон (2002); Felsner & Pergel (2008). Бонаның қосымша сілтемелерін де қараңыз.

[3] Кнут (1968); Ротем (1981).

[rotem81-4] а ^б Ротем (1981).

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

[6] Мишели және Россин (2006).

[1]

[2]

[3]

[4]

[5]

[6]