Andrei Asinowski ; Cyril Banderier ; Benjamin Hackl - Flip-sort and combinatorial aspects of pop-stack sorting

dmtcs:6196 - Discrete Mathematics & Theoretical Computer Science, April 30, 2021, vol. 22 no. 2, Permutation Patterns 2019 - https://doi.org/10.46298/dmtcs.6196
Flip-sort and combinatorial aspects of pop-stack sorting

Authors: Andrei Asinowski ; Cyril Banderier ; Benjamin Hackl

    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.


    Volume: vol. 22 no. 2, Permutation Patterns 2019
    Section: Special issues
    Published on: April 30, 2021
    Accepted on: April 7, 2021
    Submitted on: March 12, 2020
    Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics,05A05, 05A19, 05A15, 05A16

    Linked data

    Source : ScholeXplorer HasVersion DOI 10.48550/arxiv.2003.04912
    • 10.48550/arxiv.2003.04912
    Flip-sort and combinatorial aspects of pop-stack sorting
    Asinowski, Andrei ; Banderier, Cyril ; Hackl, Benjamin ;

    Share

    Consultation statistics

    This page has been seen 375 times.
    This article's PDF has been downloaded 155 times.