Following the footprints of what have been done with the algorithm Stacksort, we investigate the preimages of the map associated with a slightly less well known algorithm, called Queuesort. Our results include a recursive description of the set of all preimages of a given permutation, a characterization of allowed cardinalities for preimages, the exact enumeration of permutations having 0, 1 and 2 preimages, respectively, and, finally, a closed formula for the number of preimages of those permutations whose left-to-right maxima are concentrated at the beginning and at the end.

Characterization and Enumeration of Preimages Under the Queuesort Algorithm / Cioni L.; Ferrari L.. - STAMPA. - (2021), pp. 234-240. [10.1007/978-3-030-83823-2_37]

Characterization and Enumeration of Preimages Under the Queuesort Algorithm

Cioni L.;Ferrari L.
2021

Abstract

Following the footprints of what have been done with the algorithm Stacksort, we investigate the preimages of the map associated with a slightly less well known algorithm, called Queuesort. Our results include a recursive description of the set of all preimages of a given permutation, a characterization of allowed cardinalities for preimages, the exact enumeration of permutations having 0, 1 and 2 preimages, respectively, and, finally, a closed formula for the number of preimages of those permutations whose left-to-right maxima are concentrated at the beginning and at the end.
2021
978-3-030-83822-5
978-3-030-83823-2
Trends in Mathematics
234
240
Cioni L.; Ferrari L.
File in questo prodotto:
File Dimensione Formato  
cioni_ferrari_final.pdf

Accesso chiuso

Descrizione: Articolo principale
Tipologia: Pdf editoriale (Version of record)
Licenza: Tutti i diritti riservati
Dimensione 262.51 kB
Formato Adobe PDF
262.51 kB Adobe PDF   Richiedi una copia

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/1247192
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact