HOME

TheInfoList



OR:

In mathematics and
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, a stack-sortable permutation (also called a tree permutation) is a
permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or p ...
whose elements may be sorted by an algorithm whose internal storage is limited to a single
stack data structure In computer science, a stack is an abstract data type that serves as a collection of elements, with two main operations: * Push, which adds an element to the collection, and * Pop, which removes the most recently added element that was not y ...
. The stack-sortable permutations are exactly the permutations that do not contain the
permutation pattern In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the ...
231; they are counted by the
Catalan number In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles C ...
s, and may be placed in bijection with many other combinatorial objects with the same counting function including
Dyck path In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Ca ...
s and
binary tree In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binar ...
s.


Sorting with a stack

The problem of sorting an input sequence using a stack was first posed by , who gave the following
linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
algorithm (closely related to algorithms for the later
all nearest smaller values In computer science, the all nearest smaller values problem is the following task: for each position in a sequence of numbers, search among the previous positions for the last position that contains a smaller value. This problem can be solved effici ...
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 A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should oc ...
, 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 In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or p ...
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 In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the ...
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 pattern In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the ...
s 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 In the theory of formal languages of computer science, mathematics, and linguistics, a Dyck word is a balanced string of square brackets and The set of Dyck words forms the Dyck language. Dyck words and language are named after the mathematic ...
: 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 2''n'', the
Catalan number In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles C ...
:C_n = \frac\binom. Stack-sortable permutations may also be translated directly to and from (unlabeled)
binary tree In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binar ...
s, another
combinatorial class In mathematics, a combinatorial class is a countable set of mathematical objects, together with a size function mapping each object to a non-negative integer, such that there are finitely many objects of each size. Counting sequences and isomorphi ...
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 Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematic ...
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 noted, the 123-avoiding and 321-avoiding permutations also have the same counting function despite being less directly related to the stack-sortable permutations.


Random stack-sortable permutations

investigates the properties of stack-sortable permutations chosen uniformly at random among all such permutations of a given length. The expected length of the longest descending subsequence in such a permutation is \sqrt-O(1), differing by a constant factor from unconstrained random permutations (for which the expected length is approximately 2\sqrt n). The expected length of the longest ascending sequence differs even more strongly from unconstrained permutations: it is (n+1)/2. The expected number of values within the permutation that are larger than all previous values is only 3 - 6/(n+2), smaller than its logarithmic value for unconstrained permutations. And the expected number of inversions is \Theta(n^), in contrast to its value of \Theta(n^2) for unconstrained permutations.


Additional properties

Every permutation defines a
permutation graph In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be de ...
, a graph whose vertices are the elements of the permutation and whose edges connect pairs of elements that are inverted by the permutation. The permutation graphs of stack-sortable permutations are trivially perfect. For each element ''i'' of a permutation ''p'', define ''bi'' to be the number of other elements that are to the left of and greater than ''i''. Then ''p'' is stack-sortable if and only if, for all ''i'', ''bi'' − ''b''''i'' + 1 ≤ 1.


Algorithms

uses the bijection between stack-sortable permutations and binary trees to define a numerical rank for each binary tree, and to construct efficient algorithms for computing the rank of a tree ("ranking") and for computing the tree with a given rank ("unranking"). defined two edit operations on permutations: deletion (making a
permutation pattern In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the ...
) and its inverse. Using the same correspondence between trees and permutations, they observed that these operations correspond to
edge contraction In graph theory, an edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. Edge contraction is a fundamental operation in the theory of graph minors. Vertex id ...
in a tree and its inverse. By applying a
polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
dynamic programming Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. I ...
algorithm for
edit distance In computational linguistics and computer science, edit distance is a string metric, i.e. a way of quantifying how dissimilar two strings (e.g., words) are to one another, that is measured by counting the minimum number of operations required to t ...
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 permutation In combinatorial mathematics, a separable permutation is a permutation that can be obtained from the trivial permutation 1 by direct sums and skew sums. Separable permutations may be characterized by the forbidden permutation patterns 2413 and 31 ...
s; however, the longest common pattern problem is NP-complete for arbitrary permutations..


Notes


References

*. *. *. *. *. *. *. * *. *{{citation , last = Tarjan , first = Robert , authorlink = Robert Tarjan , date = April 1972 , doi = 10.1145/321694.321704 , issue = 2 , journal =
Journal of the ACM The ''Journal of the ACM'' is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief An editor-in-c ...
, pages = 341–346 , title = Sorting Using Networks of Queues and Stacks , volume = 19, doi-access = free . Permutation patterns