Sorting permutations using a pop stack with a bypass
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917951372787712 |
|---|---|
| author | Cioni, Lapo Ferrari, Luca Smith, Rebecca |
| author_facet | Cioni, Lapo Ferrari, Luca Smith, Rebecca |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_08285 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sorting permutations using a pop stack with a bypass Cioni, Lapo Ferrari, Luca Smith, Rebecca Discrete Mathematics Combinatorics 05A05, 05A10, 05A15 G.2.1 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. |
| title | Sorting permutations using a pop stack with a bypass |
| topic | Discrete Mathematics Combinatorics 05A05, 05A10, 05A15 G.2.1 |
| url | https://arxiv.org/abs/2503.08285 |