资源描述：
《Bona---A survey of stack-sorting disciplines.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、Asurveyofstack-sortingdisciplinesMikl´osB´onaDepartmentofMathematics,UniversityofFloridaGainesvilleFL32611-8105bona@math.ufl.edu∗Submitted:May19,2003;Accepted:Jun18,2003;Published:Jul27,2003MRSubjectClassifications:05A15,05A16AbstractWereviewthevariouswaysthatstacks,
2、theirvariationsandtheircombinations,havebeenusedassortingdevices.Inparticular,weshowthattheyhavebeenakeymotivatorforthestudyofpermutationpatterns.WealsoshowthattheyhaveconnectionstootherareasincombinatoricssuchasYoungtableau,planargraphtheory,andsimplicialcomplexes.
3、1IntroductionThestacksortingproblemintroducedbyKnuth[29]inthe1960’swasafoundinginspi-rationinthestudyofpermutationpatterns.Simultaneouslyitintroducedthenotionofpatterncontainment,definingaclassofpermutationsbyaforbiddenset,andtheenu-merationofpermutationsinsuchclasse
4、s.SoonafterwardsvariousgeneralizationsbyTarjan[36],Pratt[33],andEvenandItai[24]werestudiedandtheseauthorsposedquestionsaboutpermutationpatternswhicheventodaycannotbeeasilyanswered.But,fromaround1973throughto1992whenHerbertWilfdeliveredaninfluentialaddresstotheSIAMmee
5、tingonDiscreteMathematics,thesequestionslayalmostuntouched.The1990’sandthenewmilleniumsawarenaissanceofpermutationpatternresearchandstacksortingproblemsreturnedasoneofitsmaindrivers.Inthissurveyweshallreviewboththeearlyworkandmorerecentworkonstacksorting.Weshallseet
6、hatittouchesonmanyareasofcombinatoricsandremainsafascinatingsourceofopenproblems.∗SupportedbyaYoungInvestigatorGrantoftheNationalSecurityAgency.Thepaperwaswrittenduringaone-monthstayoftheauthoratLABRI,attheUniversityofBordeauxI,France.theelectronicjournalofcombinato
7、rics9(2)(2003),#A11Astackisalast-in,first-outlinearsequenceaccessedatoneendcalledthetop.Itemsareaddedandremovedfromthetopendbypushandpopoperations.Initssimplestformastackisusedtorearrangeapermutationp=p1,p2,...,pnasfollows.Theelementsofparepushedontoaninitiallyemptys
8、tackandanoutputpermutationisformedbypoppingelementsfromthestack.Theoutputpermutationobviouslydependsonhowthepushandpopoperationsareinterle
