Stack-sortable permutation
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): 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.
As well as inspiring much subsequent work on sorting using more complicated systems of stacks and related data structures,[2] Knuth's research kicked off the study of permutation patterns and of permutation classes defined by forbidden patterns.
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.
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.
The expected length of the longest descending subsequence in such a permutation is
, differing by a constant factor from unconstrained random permutations (for which the expected length is approximately
The expected length of the longest ascending sequence differs even more strongly from unconstrained permutations: it is
By applying a polynomial time dynamic programming algorithm for edit distance in trees, they showed that the edit distance between two stack-sortable permutations (and hence also the longest common pattern) can be found in polynomial time.
This technique was later generalized to algorithms for finding longest common patterns of separable permutations;[5] however, the longest common pattern problem is NP-complete for arbitrary permutations.
