Flip-sort and combinatorial aspects of pop-stack sorting
Copyright policy )Flip-sort and combinatorial aspects of pop-stack sorting
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.
- University of Klagenfurt Austria
- Université Sorbonne Paris Nord - Paris 13 France
- MEDIZINISCHE UNIVERSITAT GRAZ Austria
- Paris 13 University France
- UNIVERSITE DE PARIS-SORBONNE (PARIS IV) France
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Formal Languages and Automata Theory (cs.FL), mathematics - combinatorics, Exact enumeration problems, generating functions, Computer Science - Formal Languages and Automata Theory, Formal languages and automata, permutation, Computer Science - Data Structures and Algorithms, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), 05a05, 05a19, 05a15, 05a16, Permutations, words, matrices, Combinatorics in computer science, generating tree, finite automaton, computer science - discrete mathematics, lattice path, generating function, stack sorting, Combinatorics (math.CO), Searching and sorting, Mathematics, Computer Science - Discrete Mathematics, 05A05, 05A19, 05A15, 05A16
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Formal Languages and Automata Theory (cs.FL), mathematics - combinatorics, Exact enumeration problems, generating functions, Computer Science - Formal Languages and Automata Theory, Formal languages and automata, permutation, Computer Science - Data Structures and Algorithms, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), 05a05, 05a19, 05a15, 05a16, Permutations, words, matrices, Combinatorics in computer science, generating tree, finite automaton, computer science - discrete mathematics, lattice path, generating function, stack sorting, Combinatorics (math.CO), Searching and sorting, Mathematics, Computer Science - Discrete Mathematics, 05A05, 05A19, 05A15, 05A16
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).4 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!