[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/stack-sortable-permutation-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki24\/stack-sortable-permutation-wikipedia\/","headline":"Stack-sortable permutation – Wikipedia","name":"Stack-sortable permutation – Wikipedia","description":"In mathematics and computer science, a stack-sortable permutation (also called a tree permutation)[1] is a permutation whose elements may be","datePublished":"2015-03-08","dateModified":"2015-03-08","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki24\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/a0d98ac30d7bfc614f59144562682f56fd7833b9","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/a0d98ac30d7bfc614f59144562682f56fd7833b9","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en\/wiki24\/stack-sortable-permutation-wikipedia\/","wordCount":3821,"articleBody":"In mathematics and computer science, a stack-sortable permutation (also called a tree permutation)[1] 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.Table of ContentsSorting with a stack[edit]Bijections and enumeration[edit]Random stack-sortable permutations[edit]Additional properties[edit]Algorithms[edit]References[edit]Sorting with a stack[edit]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 stackFor 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 outputPush x onto the stackWhile the stack is nonempty, pop it to the outputKnuth 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\u00a0O(1){displaystyle {sqrt {pi n}}-O(1)}, differing by a constant factor from unconstrained random permutations (for which the expected length is approximately 2n{displaystyle 2{sqrt {n}}}). The expected length of the longest ascending sequence differs even more strongly from unconstrained permutations: it is  (n+1)\/2{displaystyle (n+1)\/2}. The expected number of values within the permutation that are larger than all previous values is only 3\u22126\/(n+2){displaystyle 3-6\/(n+2)}, smaller than its logarithmic value for unconstrained permutations. And the expected number of inversions is \u0398(n3\/2){displaystyle Theta (n^{3\/2})}, in contrast to its value of \u0398(n2){displaystyle Theta (n^{2})} for unconstrained permutations.Additional properties[edit]Every permutation defines a permutation graph, 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.[4]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\u00a0\u2212\u00a0bi\u00a0+\u00a01\u00a0\u2264\u00a01.[1]Algorithms[edit]Knott (1977) 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”).Micheli & Rossin (2006) defined two edit operations on permutations: deletion (making a permutation pattern) and its inverse. Using the same correspondence between trees and permutations, they observed that these operations correspond to edge contraction in a tree and its inverse. 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.[6]References[edit]Avis, David; Newborn, Monroe (1981), “On pop-stacks in series”, Utilitas Mathematica, 19: 129\u2013140, MR\u00a00624050.B\u00f3na, Mikl\u00f3s (2002), “A survey of stack-sorting disciplines”, Electronic Journal of Combinatorics, 9 (2): A1, MR\u00a02028290.Bouvel, Mathilde; Rossin, Dominique; Vialette, St\u00e9phane (2007), “Longest common separable pattern among permutations”, Combinatorial Pattern Matching (CPM 2007), Lecture Notes in Computer Science, vol.\u00a04580, Springer, pp.\u00a0316\u2013327, doi:10.1007\/978-3-540-73437-6_32.Felsner, Stefan; Pergel, Martin (2008), “The complexity of sorting with networks of stacks and queues”, Proc. 16th Eur. Symp. Algorithms, Karlsruhe, Germany, pp.\u00a0417\u2013429, doi:10.1007\/978-3-540-87744-8_35, ISBN\u00a0978-3-540-87743-1.Knott, Gary D. (February 1977), “A numbering system for binary trees”, Communications of the ACM, 20 (2): 113\u2013115, doi:10.1145\/359423.359434.Knuth, Donald (1968), “Vol. 1: Fundamental Algorithms”, The Art of Computer Programming, Reading, Mass.: Addison-Wesley.Micheli, Anne; Rossin, Dominique (2006), “Edit distance between unlabeled ordered trees”, Theoretical Informatics and Applications, 40 (4): 593\u2013609, arXiv:math\/0506538, doi:10.1051\/ita:2006043, MR\u00a02277052.Rosenstiehl, Pierre; Tarjan, Robert E. (1984), “Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations”, Journal of Algorithms, 5 (3): 375\u2013390, doi:10.1016\/0196-6774(84)90018-X, MR\u00a00756164Rotem, D. (1981), “Stack sortable permutations”, Discrete Mathematics, 33 (2): 185\u2013196, doi:10.1016\/0012-365X(81)90165-5, MR\u00a00599081.Tarjan, Robert (April 1972), “Sorting Using Networks of Queues and Stacks”, Journal of the ACM, 19 (2): 341\u2013346, doi:10.1145\/321694.321704."},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/stack-sortable-permutation-wikipedia\/#breadcrumbitem","name":"Stack-sortable permutation – Wikipedia"}}]}]