We introduce a new sorting device for permutations, which we call popqueue. It consists of a special queue, having the property that any time one wants to extract elements from the queue, actually all the elements currently in the queue are poured into the output. We illustrate two distinct optimal algorithms, called Min and Cons, to sort a permutation using such a device, which allow us also to characterize sortable permutations in terms of pattern avoidance. We next investigate what happens by making two passes through a popqueue, showing that the set of sortable permutations is not a class for Min, whereas it is for Cons. In the latter case we also explicitly find the basis of the class of sortable permutations. Finally, we study preimages under Cons (by means of an equivalent version of the algorithm), and find a characterization of the set of preimages of a given permutation. We also give some enumerative results concerning the number of permutations having k preimages, for k = 1, 2, 3, and we conclude by observing that there exist permutations having k preimages for any value of k ≥ 0.

Sorting with a popqueue / Cioni, Lapo; Ferrari, Luca. - In: RAIRO. INFORMATIQUE THEORIQUE ET APPLICATIONS. - ISSN 0988-3754. - ELETTRONICO. - 58:(2024), pp. 13.0-13.0. [10.1051/ita/2024010]

Sorting with a popqueue

Cioni, Lapo;Ferrari, Luca
2024

Abstract

We introduce a new sorting device for permutations, which we call popqueue. It consists of a special queue, having the property that any time one wants to extract elements from the queue, actually all the elements currently in the queue are poured into the output. We illustrate two distinct optimal algorithms, called Min and Cons, to sort a permutation using such a device, which allow us also to characterize sortable permutations in terms of pattern avoidance. We next investigate what happens by making two passes through a popqueue, showing that the set of sortable permutations is not a class for Min, whereas it is for Cons. In the latter case we also explicitly find the basis of the class of sortable permutations. Finally, we study preimages under Cons (by means of an equivalent version of the algorithm), and find a characterization of the set of preimages of a given permutation. We also give some enumerative results concerning the number of permutations having k preimages, for k = 1, 2, 3, and we conclude by observing that there exist permutations having k preimages for any value of k ≥ 0.
2024
58
0
0
Cioni, Lapo; Ferrari, Luca
File in questo prodotto:
File Dimensione Formato  
ita220051.pdf

accesso aperto

Tipologia: Pdf editoriale (Version of record)
Licenza: Open Access
Dimensione 1.4 MB
Formato Adobe PDF
1.4 MB Adobe PDF

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1356565
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact