Originators: R. Tarjan, J. West, E. Egge, T. Mansour (presented by Daniel McDonald - REGS 2011)
Definitions:
A stack is a list where the addition of new items (called
pushing) and the removal of existing items (called popping) both
take place at the same end, referred to as the top of the stack.
Given an input list π of distinct numbers, let s(π) denote
the output obtained by the following algorithm: (1) Push the first element
x of the remaining input onto the stack if the stack is empty or
x is smaller than the top element of the stack. (2) Otherwise, pop the
top element of the stack onto the end of the output list. Repeat until the
input list and stack are empty. Note that s can be defined recursively
by s(Ø)=Ø and s(LxR)=s(L)s(R)x, where x is
the largest element of the list LxR.
Let St be the family of permutations π (written as lists) such that the result of passing through the stack algorithm t times (that is, the tth iterate st(π)) is the identity permutation. The permutations in St have been called the t-stack-sortable permutations, although here we really just use one stack repeatedly, in series.
Alternatively, we may allow t stacks in parallel. Again the sorting procedure is deterministic: Let x be the first element of the remaining input. (1) If some stack is empty, then push x onto an empty stack. (2) If no stack is empty and x is larger than the tops of all stacks, then pop the smallest top element. (3) If no stack is empty and x is smaller than some top element, then push x onto the stack with the smallest top element larger than x. Let Pt be the family of permutations such that one pass through t stacks in parallel produces the identity permutation; these are the t*-stack-sortable permutations.
Note that S1=P1; these permutations are simply called stack-sortable. In our definition of St and Pt, a larger element can never be placed on top of a smaller element. When using multiple stacks in series or parallel, more general procedures may be considered. A natural model for this is a "train siding". A siding is still last-in-first-out storage, but there is no restriction on the order of items occupying the siding. Thus we may discuss the t-siding-sortable (in series) or t*-siding-sortable permutations.
When π and τ are permutations of [n] and [m] with m≤n, we say that pattern τ occurs in &pi if some m elements of π occur in the order specified by τ; otherwise, π avoids τ. (For example, 21453876 avoids 312 but not 1243).
Background: It has long been known (discussed thoroughly in [K]), that permutations are stack-sortable if and only if they avoid 312, and the number of such permutations of [n] is the nth Catalan number C(2n,n)/(n+1), where C(m,k) denotes the binomial coefficient. J. West [W] proved that permutations are 2-stack-sortable if and only if they avoid 2341 and do not have the pattern 3241 occurring without a larger element between the first two elements. Zeilberger [Z] proved that there are 2C(3n,n)/[(n+1)(2n+1)] such permutations. All permutations of [n] are (n-1)-stack-sortable, and those in Sn-1 but not Sn-2 are the permutations ending with n1, of which there are (n-2)!. There are (7/2)(n-2)!+(n-3)! permutations of [n] in Sn-2-Sn-3. [AMR] gives a characterization of and a generating function for S2. [EM] presents enumerative results on permutations in S2 satisfying additional restrictions.
Problem 1: Characterize the permutations in S3.
Problem 2: Count the permutations of [n] in Sn-3-Sn-4.
Problem 3: For fixed d with d≥2, find the generating function in which the coefficient of xn is the number of 2-stack-sortable permutations of [n] avoiding 132, 12...d, and 213...d.
Problem 4: Find the generating function inwhich the coefficient of xn is the number of 2-stack-sortable permutations of [n] satisfying some specified permutation statistic, such as a restriction on the number of rises, descents, left-to-right maxima, left-to-right minima, right-to-left maxima, or right-to-left minima.
Problem 5: Count the 2-stack-sortable permutations containing exactly r occurrences of pattern 132.
Comments: Problems 3, 4, and 5 were posed at the end of [EM] as suggested generalizations of results in that paper that could likely be obtained using techniques like those in the paper.
For the parallel case, REGS students have proved that a permutation is t*-stack-sortable if and only if it avoids the pattern 2,3,⋅⋅⋅t+2,1. The permutation n-1,n-2,⋅⋅⋅2,n,1 is 2*-stack-sortable but is not (n-2)-stack-sortable.
Conjecture 6: The minimum number of stacks in series needed to sort a permutation is always at least as large as the number in parallel needed to sort it.
Next consider the more general algorithm we described as using sidings. Tarjan [T] gave an upper bound on how many sidings in series would be needed to sort a permutation of a given size as well as a characterization of the permutations that can be sorted by sidings in parallel subject to the constraint that everything in the input list must be pushed onto stacks before anything can be popped to the output list.
Problem 7: Which permutations are t-siding-sortable, and how many such permutations of [n] are there?
Problem 8: Which permutations are t*-siding-sortable, and how many such permutations of [n] are there?
References:
[AMR] Atkinson; Murphy; Ruskuc; Sorting with two ordered stacks in series.
Theoretical Computer Science, 289 (2002), 205-223.
[EM] Egge, Eric; Mansour, Toufik. 132-Avoiding Two-stack Sortable Permutations,
Fibonacci Numbers, and Pell Numbers. Discrete Applied Mathematics 143 (2004),
72-83.
[K] D. Knuth, The Art of Computer Programming, Volume ??
[T] Tarjan, Robert. Sorting Using Networks of Queues and Stacks. Journal of the
ACM 19 (1972), 341-346.
[W] West, Julian. Sorting twice through a stack. Theoretical Computer Science,
117 (1993), 303-313.