论文标题
流行堆栈分类的翻转和组合方面
Flip-sort and combinatorial aspects of pop-stack sorting
论文作者
论文摘要
Flip-Sort是一种自然的分类程序，可以提出引人入胜的组合问题。它在基于堆栈的排序算法上的Knuth的开创性工作中发现了根源，并导致许多与置换模式的联系。我们介绍了几个结构性，列举和算法结果，这些结果几乎不需要（分析）该程序进行分类的排列。特别是，我们给出了一次迭代后的排列形状，并表征了几个与最佳和最坏情况相关的置换率家族。 En Passant，我们还提供了流行堆栈分类，自动机和晶格路径之间的一些联系，并引入了具有自身兴趣的几种迹象证明的策略。
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.
