Iterator - Maple Programming Help

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

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

The iterator object has the following methods. The self parameter is the iterator object.

 • length(self): returns the length of the iterator Array.
 • 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):$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}V\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}M\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{printf}\left("%d\n",V\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$
 0 1 2 3 0 1 2 2 0 1 2 1 0 1 2 0 0 1 1 1 0 1 1 0 0 1 0 3 0 1 0 0 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.