Séminaire Lotharingien de Combinatoire, 85B.31 (2021), 12 pp.
Vincent Pilaud, Viviane Pons and Daniel Tamayo Jiménez
Permutree Sorting
Abstract.
Generalizing stack sorting and c-sorting for permutations, we define the permutree sorting algorithm.
Given two disjoint subsets U and D of {2, ..., n-1}, the (U,D)-permutree sorting tries to sort a permutation π ∈ Sn and fails if and only if there are 1 ≤ i < j < k ≤ n such that π contains the subword jki with j ∈ U or kij with j ∈ D.
This algorithm is seen as a way to explore an automaton which either rejects all reduced words of π, or accepts those reduced words for π whose prefixes are all (U,D)-permutree sortable.
Received: December 1, 2020.
Accepted: March 1, 2021.
Final version: April 29, 2021.
The following versions are available: