Sorting and preimages of pattern classes

MaRDI QIDQ5377411zbMATH OpenFDO

Authors Anders Claesson, Henning Úlfarsson

Publication date 24 May 2019

Full work available at URL https://arxiv.org/abs/1203.2437, http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAR0153

zbMATH Keywords

permutation patternssorting algorithms

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Searching and sorting (68P10) Algorithms in computer science (68W99)

Abstract: We introduce an algorithm to determine when a sorting operation, such as stack-sort or bubble-sort, outputs a given pattern. The algorithm provides a new proof of the description of West-2-stack-sortable permutations, that is permutations that are completely sorted when passed twice through a stack, in terms of patterns. We also solve the long-standing problem of describing West-3-stack-sortable permutations. This requires a new type of generalized permutation pattern we call a decorated pattern.

Recommendations

• Describing West-3-stack-sortable permutations with permutation patterns
• Stack-sorting preimages of permutation classes
• Stack-sortable permutations and beyond
• A survey of stack sortable permutations
• A survey of stack-sorting disciplines

Cited in

(29)

• Sorted and/or sortable permutations
• Preimages under the Queuesort algorithm
• Restricted stacks as functions
• Preimages under the bubblesort operator
• Polyurethane toggles
• Stack-sorting preimages of permutation classes
• Uniquely sorted permutations
• Counting 3-stack-sortable permutations
• Preimages under the stack-sorting algorithm
• Bubblesort, stacksort and their duals
• Sorting classes
• Stack-sortable permutations and beyond
• Postorder Preimages
• Restricted patience sorting and barred pattern avoidance
• Stack-sorting for words
• Refined enumeration of permutations sorted with two stacks and a D₈-symmetry
• On the inverse image of pattern classes under bubble sort
• Operators of equivalent sorting power and related Wilf-equivalences
• Preimages under a popqueue-sorting algorithm
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• Lattice paths and pattern-avoiding uniquely sorted permutations
• A survey of stack sortable permutations
• Permutree sorting
• Permutree sorting
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• A lift of West's stack-sorting map to partition diagrams
• Deterministic stack-sorting for set partitions
• Describing West-3-stack-sortable permutations with permutation patterns
• Stack words and a bound for 3-stack sortable permutations

This page was built for publication: Sorting and preimages of pattern classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5377411)