Sorting permutations using a pop stack with a bypass
| Title: | Sorting permutations using a pop stack with a bypass |
|---|---|
| Authors: | Cioni, Lapo, Ferrari, Luca, Smith, Rebecca |
| Publication Year: | 2025 |
| Collection: | Computer Science Mathematics |
| Subject Terms: | Computer Science - Discrete Mathematics, Mathematics - Combinatorics, 05A05, 05A10, 05A15, G.2.1 |
| More Details: | We introduce a new sorting device for permutations which makes use of a pop stack augmented with a bypass operation. This results in a sorting machine, which is more powerful than the usual Popstacksort algorithm and seems to have never been investigated previously. In the present paper, we give a characterization of sortable permutations in terms of forbidden patterns and reinterpret the resulting enumerating sequence using a class of restricted Motzkin paths. Moreover, we describe an algorithm to compute the set of all preimages of a given permutation, thanks to which we characterize permutations having a small number of preimages. Finally, we provide a full description of the preimages of principal classes of permutations, and we discuss the device consisting of two pop stacks in parallel, again with a bypass operation. Comment: 29 pages, 6 figures; this is the full version of the conference paper "Pop Stacks with a Bypass", in the Proceedings of the 13th edition of the conference on Random Generation of Combinatorial Structures. Polyominoes and Tilings (GASCom 2024), Bordeaux, France, 24-28th June 2024, Electronic Proceedings in Theoretical Computer Science 403, pp. 73-78, arXiv:2406.16399v1 |
| Document Type: | Working Paper |
| Access URL: | http://arxiv.org/abs/2503.08285 |
| Accession Number: | edsarx.2503.08285 |
| Database: | arXiv |
| Description not available. |