Let B and S be, respectively, the base steps of bubblesort and stacksort, and call B ̃ and S ̃ their dual versions via the reverse-complement map. We find some unexpected commutation properties between the classical operators and their duals, and we also prove that the set of permutations sortable by a prescribed number of iterations of B and B ̃ is a pattern class.
Luca Ferrari (2014). Bubblesort, stacksort and their duals. DISCRETE APPLIED MATHEMATICS, 170, 64-71 [10.1016/j.dam.2014.01.014].
Bubblesort, stacksort and their duals
FERRARI, LUCA
2014
Abstract
Let B and S be, respectively, the base steps of bubblesort and stacksort, and call B ̃ and S ̃ their dual versions via the reverse-complement map. We find some unexpected commutation properties between the classical operators and their duals, and we also prove that the set of permutations sortable by a prescribed number of iterations of B and B ̃ is a pattern class.File in questo prodotto:
Eventuali allegati, non sono esposti
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
