Stack sorting with increasing and decreasing stacks

DOI10.37236/9154MaRDI QIDQ2288161zbMATH OpenOpenAlexFDO

Authors Giulio Cerbai, Lapo Cioni, L. Ferrari

Publication date 17 January 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1910.03578, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i1p1

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Searching and sorting (68P10)

Abstract: We introduce a sorting machine consisting of $k+1$ stacks in series: the first $k$ stacks can only contain elements in decreasing order from top to bottom, while the last one has the opposite restriction. This device generalizes cite{SM}, which studies the case $k=1$. Here we show that, for $k=2$, the set of sortable permutations is a class with infinite basis, by explicitly finding an antichain of minimal nonsortable permutations. This construction can easily be adapted to each $kge3$. Next we describe an optimal sorting algorithm, again for the case $k=2$. We then analyze two types of left-greedy sorting procedures, obtaining complete results in one case and only some partial results in the other one. We close the paper by discussing a few open questions.

Review text

Summary: We introduce a sorting machine consisting of \(k+1\) stacks in series: the first \(k\) stacks can only contain elements in decreasing order from top to bottom, while the last one has the opposite restriction. This device generalizes the \(\mathfrak{DI}\) machine introduced by Rebecca Smith, which studies the case \(k=1\). Here we show that, for \(k=2\), the set of sortable permutations is a class with infinite basis, by explicitly finding an antichain of minimal nonsortable permutations. This construction can easily be adapted to each \(k\geqslant 3\). Next we describe an optimal sorting algorithm, again for the case \(k=2\). We then analyze two types of left-greedy sorting procedures, obtaining complete results in one case and only some partial results in the other one. We close the paper by discussing a few open questions.

Recommendations

• Stack sorting with restricted stacks
• Stack-sorting with consecutive-pattern-avoiding stacks
• Sorting twice through a stack
• Sorting with two ordered stacks in series.
• Manipulating multiple stacks with ordered-heap
• Two-stack-sorting with pop stacks
• On rearrangement of items stored in stacks
• Stack-sortable permutations and beyond
• scientific article; zbMATH DE number 1796967
• A survey of stack-sorting disciplines

Cites work

• 2-stack sorting is polynomial
• A survey of stack-sorting disciplines
• Comparing algorithms for sorting with t stacks in series
• Counting 3-stack-sortable permutations
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 2107707 (Why is no real title available?)
• Patterns in permutations and words.
• Permutations sortable by two stacks in parallel and quarter plane walks
• Permutations with forbidden subsequences and a generalized Schröder number
• Postorder Preimages
• Sorted and/or sortable permutations
• Sorting Using Networks of Queues and Stacks
• Stack sorting with increasing and decreasing stacks
• Stack sorting with restricted stacks
• Stack-sorting, set partitions, and Lassalle's sequence
• Two stacks in series: a decreasing stack followed by an increasing stack

Cited in

(8)

• Stack sorting with increasing and decreasing stacks
• Stack sorting with restricted stacks
• A stack and pop stack in series
• Two stacks in series: a decreasing stack followed by an increasing stack
• Passing through a stack k times
• Sorting Cayley permutations with pattern-avoiding machines
• Dynamical aspects of \(\sigma\)-machines
• Sorting twice through a stack

Describes a project that uses

Uses Software

• OEIS
• PermLab

This page was built for publication: Stack sorting with increasing and decreasing stacks

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