Iterator - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Combinatorics : Iterator : Iterator/TopologicalSorts

Iterator

  

TopologicalSorts

  

generate permutations with restrictions

 

Calling Sequence

Parameters

Options

Description

Examples

References

Compatibility

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<y appears in rels, x precedes y in all permutations.

Examples

withIterator&colon;

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

TTopologicalSorts4&comma;1<2&comma;3<4&colon;

seqt&comma;t=T

1234,1324,1342,3124,3142,3412

(1)

Count the number of permutations that meet the restrictions.

add1&comma;t=T

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 1&comma;&comma;n such that each row is increasing from left to right and each column from top to bottom. In a permutation a&comma;&comma;an of the integers 1&comma;&comma;n x precedes y if and only if ax<ay in the inverse permutation a1&comma;&comma;an. Consequently, specifying that i<j 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.

Matrix3&comma;2&comma;seq1..6

123456

(3)

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

rels1<2&comma;1<3&comma;2<4&comma;3<4&comma;3<5&comma;4<6&comma;5<6&colon;

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

YTopologicalSorts6&comma;rels&comma;inverse&colon;

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

AArrayTools:-AliasoutputY&comma;3&comma;2&comma;C_order&colon;

seqA&comma;y=Y

123456,123546,132456,132546,142536

(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:

YoungNum3&comma;2

5

(5)

YoungNum3&comma;3

42

(6)

YoungNum4&comma;4

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.

• 

For more information on Maple 2016 changes, see Updates in Maple 2016.

See Also

Iterator

TopologicalSort