Oriented Forests - Maple Help

Iterator

 OrientedForests
 generate oriented forests of a given size

 Calling Sequence OrientedForests(n,opts)

Parameters

 n - posint; number of nodes in an oriented forest opts - (optional) equation(s) of the form option = value; specify options for the OrientedForests command

Options

 • compile = truefalse
 True means compile the iterator. The default is true.

Description

 • The OrientedForests command returns an iterator that generates all oriented forests on n-nodes, in decreasing lexicographic order of their level codes.
 • The iterator output Array contains the parent pointers, in preorder, of the nodes in the forest. If the pointer is zero, the node is the root of a tree. In the following two-tree forest, the representation is [0,1,2,0,4,5,5,4]. For example, the entry at index 8 is 4, which indicates the parent of node 8 is node 4.

Methods

In addition to the common iterator methods, this iterator object has the following methods. The self parameter is the iterator object.

 • Number(self): return the number of iterations required to step through the iterator, assuming it started at rank one.

Examples

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

Construct an iterator of oriented forests with 4 nodes.

 > $M≔\mathrm{OrientedForests}\left(4\right):$
 > $\mathrm{Print}\left(M,'\mathrm{showrank}'\right):$
 1: 0 1 2 3 2: 0 1 2 2 3: 0 1 2 1 4: 0 1 2 0 5: 0 1 1 1 6: 0 1 1 0 7: 0 1 0 3 8: 0 1 0 0 9: 0 0 0 0

Compute the number of iterations.

 > $\mathrm{Number}\left(M\right)$
 ${9}$ (1)

References

 Knuth, Donald Ervin. The Art of Computer Programming, volume 1, 3rd ed. fundamental algorithms, sec. 2.3, Trees, pp. 308-309.
 Knuth, Donald Ervin. The Art of Computer Programming, volume 1, 3rd ed. fundamental algorithms, sec. 2.3.4.4, Enumeration of Trees, pp. 386-394.
 Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 4; generating all trees, sec. 7.2.1.6, generating all trees, algorithm O, oriented forests, p. 24.

Compatibility

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