 TopologicalSorts - Maple Help

Iterator

 TopologicalSorts
 generate permutations with restrictions Calling Sequence TopologicalSorts(n,rels,opts) Parameters

 n - posint; the size of the set rels - set(<); relations restricting the permutations opts - (optional) equation(s) of the form option = value; specify options for the TopologicalSorts command Options

 • compile = truefalse
 True means compile the iterator. The default is true.
 • inverse = truefalse
 True means return the inverse permutations. False means return the normal permutations. The default is false. Description

 • The TopologicalSorts command returns an iterator that generates the permutations of the integers 1 to n that obey specified restrictions.
 • The n parameter is a positive integer that specifies the set of integers, 1 to n.
 • The rels parameter specifies the relations that restrict the permutations. The relations are true strict-inequalities between the integers 1 to n.
 • If the relation $x appears in rels, $x$ precedes $y$ in all permutations.
 • This iterator object has the common iterator methods. Examples

 > $\mathrm{with}\left(\mathrm{Iterator}\right):$

Create all permutations of the integers 1 to 4 such that 1 precedes 2, and 3 precedes 4.

 > $T≔\mathrm{TopologicalSorts}\left(4,\left\{1<2,3<4\right\}\right):$
 > $\mathrm{seq}\left(t\left[\right],t=T\right)$
 $\left[\begin{array}{cccc}{1}& {2}& {3}& {4}\end{array}\right]{,}\left[\begin{array}{cccc}{1}& {3}& {2}& {4}\end{array}\right]{,}\left[\begin{array}{cccc}{1}& {3}& {4}& {2}\end{array}\right]{,}\left[\begin{array}{cccc}{3}& {1}& {2}& {4}\end{array}\right]{,}\left[\begin{array}{cccc}{3}& {1}& {4}& {2}\end{array}\right]{,}\left[\begin{array}{cccc}{3}& {4}& {1}& {2}\end{array}\right]$ (1)

Count the number of permutations that meet the restrictions.

 > $\mathrm{add}\left(1,t=T\right)$
 ${6}$ (2) Young rectangle

A Young rectangle is a specialization of a Young tableau. It consists of an $m×n$ rectangular arrangement of the integers $\left(1,\dots ,n\right)$ such that each row is increasing from left to right and each column from top to bottom. In a permutation $\left({a}_{,}\dots ,{a}_{n}\right)$ of the integers $\left(1,\dots ,n\right)$ $x$ precedes $y$ if and only if $a{\prime }_{x} in the inverse permutation $a{\prime }_{1},\dots ,a{\prime }_{n}$. Consequently, specifying that $i means that, in all the inverse permutations, the value in position $i$ is less than that in position $j$.

Label the cells of a 3x2 matrix as shown.

 > $\mathrm{Matrix}\left(3,2,\left[\mathrm{seq}\left(1..6\right)\right]\right)$
 $\left[\begin{array}{cc}{1}& {2}\\ {3}& {4}\\ {5}& {6}\end{array}\right]$ (3)

If an inverse permutation meets the requirement of the Young rectangle, the corresponding relations are

 > $\mathrm{rels}≔\left\{1<2,1<3,2<4,3<4,3<5,4<6,5<6\right\}:$

Construct the iterator; use the inverse option to generate the inverse permutations.

 > $Y≔\mathrm{TopologicalSorts}\left(6,\mathrm{rels},\mathrm{inverse}\right):$

Generate and display the results as Matrices. Use ArrayTools[Alias] to create a 3x2 Matrix representation of the Vector output.

 > $A≔\mathrm{ArrayTools}:-\mathrm{Alias}\left(\mathrm{output}\left(Y\right),\left[3,2\right],\mathrm{C_order}\right):$
 > $\mathrm{seq}\left(A\left[\right],y=Y\right)$
 $\left[\begin{array}{cc}{1}& {2}\\ {3}& {4}\\ {5}& {6}\end{array}\right]{,}\left[\begin{array}{cc}{1}& {2}\\ {3}& {5}\\ {4}& {6}\end{array}\right]{,}\left[\begin{array}{cc}{1}& {3}\\ {2}& {4}\\ {5}& {6}\end{array}\right]{,}\left[\begin{array}{cc}{1}& {3}\\ {2}& {5}\\ {4}& {6}\end{array}\right]{,}\left[\begin{array}{cc}{1}& {4}\\ {2}& {5}\\ {3}& {6}\end{array}\right]$ (4)

Assign a procedure that counts Young rectangles of a given size.

 > YoungNum := proc(m::nonnegint,n::nonnegint) local i,j,pos,rels,Y;     pos := (i,j) -> (i-1)*n+j;     rels := {seq(seq(pos(i,j) < pos(i,j+1), j=1..n-1), i=1..m),              seq(seq(pos(i,j) < pos(i+1,j), i=1..m-1), j=1..n)             };     Y := Iterator:-TopologicalSorts(m*n, rels);     add(1, y=Y); end proc:
 > $\mathrm{YoungNum}\left(3,2\right)$
 ${5}$ (5)
 > $\mathrm{YoungNum}\left(3,3\right)$
 ${42}$ (6)
 > $\mathrm{YoungNum}\left(4,4\right)$
 ${24024}$ (7) References

 Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 2; generating all tuples and permutations, sec. 7.2.1.2, p. 63, generating all permutations, algorithm V, all topological sorts. Compatibility

 • The Iterator[TopologicalSorts] command was introduced in Maple 2016.