Geodesic
Flip-sort and combinatorial aspects of pop-stack sorting
Discrete mathematics & theoretical computer science, Permutation Patterns 2019, Tome 22 (2020-2021) no. 2.

Voir la notice de l'article provenant de la source Episciences

Flip-sort is a natural sorting procedure which raises fascinating combinatorial questions. It finds its roots in the seminal work of Knuth on stack-based sorting algorithms and leads to many links with permutation patterns. We present several structural, enumerative, and algorithmic results on permutations that need few (resp. many) iterations of this procedure to be sorted. In particular, we give the shape of the permutations after one iteration, and characterize several families of permutations related to the best and worst cases of flip-sort. En passant, we also give some links between pop-stack sorting, automata, and lattice paths, and introduce several tactics of bijective proofs which have their own interest. 
@article{DMTCS_2021_22_2_a4,
     author = {Asinowski, Andrei and Banderier, Cyril and Hackl, Benjamin},
     title = {Flip-sort and combinatorial aspects of pop-stack sorting},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2020-2021},
     doi = {10.46298/dmtcs.6196},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6196/}
}
TY  - JOUR
AU  - Asinowski, Andrei
AU  - Banderier, Cyril
AU  - Hackl, Benjamin
TI  - Flip-sort and combinatorial aspects of pop-stack sorting
JO  - Discrete mathematics & theoretical computer science
PY  - 2020-2021
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6196/
DO  - 10.46298/dmtcs.6196
LA  - en
ID  - DMTCS_2021_22_2_a4
ER  - 
%0 Journal Article
%A Asinowski, Andrei
%A Banderier, Cyril
%A Hackl, Benjamin
%T Flip-sort and combinatorial aspects of pop-stack sorting
%J Discrete mathematics & theoretical computer science
%D 2020-2021
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6196/
%R 10.46298/dmtcs.6196
%G en
%F DMTCS_2021_22_2_a4
Asinowski, Andrei; Banderier, Cyril; Hackl, Benjamin. Flip-sort and combinatorial aspects of pop-stack sorting. Discrete mathematics & theoretical computer science, Permutation Patterns 2019, Tome 22 (2020-2021) no. 2. doi : 10.46298/dmtcs.6196. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6196/

Cité par Sources :