In mathematics and computer science, a stack-sortable permutation (also called a tree permutation) is a permutation whose elements may be sorted by an algorithm whose internal storage is limited to a single stack data structure. The stack-sortable permutations are exactly the permutations that do not contain the permutation pattern 231; they are counted by the Catalan numbers, and may be placed in bijection with many other combinatorial objects with the same counting function including Dyck paths and binary trees.
Sorting with a stack The problem of sorting an input sequence using a stack was first posed by Knuth (1968), who gave the following linear time algorithm (closely related to algorithms for the later all nearest smaller values problem):
Initialize an empty stack For each input value x: While the stack is nonempty and x is larger than the top item on the stack, pop the stack to the output Push x onto the stack While the stack is nonempty, pop it to the output Knuth observed that this algorithm correctly sorts some input sequences, and fails to sort others. For instance, the sequence 3,2,1 is correctly sorted: the three elements are all pushed onto the stack, and then popped in the order 1,2,3. However, the sequence 2,3,1 is not correctly sorted: the algorithm first pushes 2, and pops it when it sees the larger input value 3, causing 2 to be output before 1 rather than after it. Because this algorithm is a comparison sort, its success or failure does not depend on the numerical values of the input sequence, but only on their relative order; that is, an input may be described by the permutation needed to form that input from a sorted sequence of the same length. Knuth characterized the permutations that this algorithm correctly sorts as being exactly the permutations that do not contain the permutation pattern 231: three elements x, y, and z, appearing in the input in that respective order, with z < x < y. Moreover, he observed that, if the algorithm fails to sort an input, then that input cannot be sorted with a single stack. As well as inspiring much subsequent work on sorting using more complicated systems of stacks and related data structures, Knuth's research kicked off the study of permutation patterns and of permutation classes defined by forbidden patterns.
Bijections and enumeration The sequence of pushes and pops performed by Knuth's sorting algorithm as it sorts a stack-sortable permutation form a Dyck language: reinterpreting a push as a left parenthesis and a pop as a right parenthesis produces a string of balanced parentheses. Moreover, every Dyck string comes from a stack-sortable permutation in this way, and every two different stack-sortable permutations produce different Dyck strings. For this reason, the number of stack-sortable permutations of length n is the same as the number of Dyck strings of length 2n, the Catalan number
C n = 1 n + 1 ( 2 n n ) . {\displaystyle C_{n}={\frac {1}{n+1}}{\binom {2n}{n}}.}
Stack-sortable permutations may also be translated directly to and from (unlabeled) binary trees, another combinatorial class whose counting function is the sequence of Catalan numbers. A binary tree may be transformed into a stack-sortable permutation by numbering its nodes in left-to-right order, and then listing these numbers in the order they would be visited by a preorder traversal of the tree: the root first, then the left subtree, then the right subtree, continuing recursively within each subtree. In the reverse direction, a stack-sortable permutation may be decoded into a tree in which the first value x of the permutation corresponds to the root of the tree, the next x − 1 values are decoded recursively to give the left child of the root, and the remaining values are again decoded recursively to give the right child. Several other classes of permutations may also be placed in bijection with the stack-sortable permutations. For instance, the permutations that avoid the patterns 132, 213, and 312 may be formed respectively from the stack-sortable (231-avoiding) permutations by reversing the permutation, replacing each value x in the permutation by n + 1 − x, or both operations combined. The 312-avoiding permutations are also the inverses of the 231-avoiding permutations, and have been called the stack-realizable permutations as they are the permutations that can be formed from the identity permutation by a sequence of push-from-input and pop-to-output operations on a stack. As Knuth (1968) noted, the 123-avoiding and 321-avoiding permutations also have the same counting function despite being less directly related to the stack-sortable permutations.
… excerpt ends here. Continue reading the full article.
