×

Stack sorting with increasing and decreasing stacks. (English) Zbl 1430.68063

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.

MSC:

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

Software:

PermLab; OEIS
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] M. Albert,PermLab: Software for Permutation Patterns, at http://www.cs.otago.ac.nz/staffpriv/malbert/permlab.php
[2] M. Albert, M. Bousquet-M´elou,Permutations sortable by two stacks in parallel and quarter plane walks, European J. Combin., 43 (2015) 131-164. · Zbl 1301.05005
[3] M. Bona,A survey of stack sorting disciplines, Electron. J. Combin., 9(2) (2002-2003) #A1. · Zbl 1028.05003
[4] M. Bona,Combinatorics of Permutations, Discrete Mathematics and Its Applications, CRC Press, 2004. · Zbl 1052.05001
[5] M. Bousquet-M´elou,Sorted and/or sortable permutations, Discrete Math., 225 (2000) 25-50. · Zbl 0961.05001
[6] G. Cerbai, L. Cioni, L. Ferrari,Stack sorting with increasing and decreasing stacks, arXiv:1910.03578. · Zbl 1430.68063
[7] G. Cerbai,A. Claesson,L. Ferrari,Stack sorting with restricted stacks, arXiv:1907.08142. · Zbl 1435.05004
[8] C. Defant,Postorder preimages, Discrete Math. Theor. Comput. Sci., 19 (2017) #3, 15 pp. · Zbl 1397.05010
[9] C. Defant,Counting 3-stack-sortable permutations,arXiv:1903.09138. · Zbl 1433.05005
[10] C. Defant, M. Engen, J. A. Miller,Stack-sorting, set partitions, and Lassalle’s sequence,arXiv:1809.01340. · Zbl 1442.05006
[11] S. Kitaev,Patterns in permutations and words, Monographs in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg, 2011. · Zbl 1257.68007
[12] D. E. Knuth,The art of computer programming, vol. 1, Fundamental Algorithms, Addison-Wesley, Reading, Massachusetts, 1973. · Zbl 0302.68010
[13] D. Kremer,Permutations with forbidden subsequences and a generalized Schr¨oder number, Discrete Math., 218 (2000) 121-130. · Zbl 0949.05003
[14] M. Murphy,Restricted permutations, antichains, atomic classes, and stack sorting, Doctoral Thesis, University of St Andrews, 2002.
[15] A. Pierrot, D. Rossin,2-stack sorting is polynomial, Theory Comput. Syst., 60 (2017) 552-579. · Zbl 1429.68055
[16] N. J. A. Sloane,The On-Line Encyclopedia of Integer Sequences, atoeis.org. · Zbl 1044.11108
[17] R. Smith,Comparing algorithms for sorting withtstacks in series, Ann. Comb., 8 (2004) 113-121. · Zbl 1055.05001
[18] R. Smith,Two stacks in series: a decreasing stack followed by an increasing stack, Ann. Comb., 18 (2014) 359-363. · Zbl 1297.05011
[19] R. E. Tarjan,Sorting using networks of queues and stacks, Journal of the ACM, 19 (1972) 341-346. · Zbl 0243.68004
[20] J. West,Permutations with forbidden subsequences and stack-sortable permutations, PhD thesis, Massachusetts Institute of Technology, 1990.
[21] J. · JFM 45.0027.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.