 Iterator - Maple Programming Help

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

Iterator

 NearPerfectParentheses
 generate positions of left-parentheses in pairs of nested parentheses

 Calling Sequence NearPerfectParentheses(n)

Parameters

 n - integer greater than 1

Options

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

Description

 • The NearPerfectParentheses command returns an iterator that generates all n-combinations of the integers $1..2n$ that represent the positions of left parentheses in a string of n-pairs of nested parentheses. For example, the string $"\left(\right)\left(\right)\left(\right)"$ is represented by $\left[1,3,5\right]$, while $"\left(\left(\left(\right)\right)\right)"$ is represented by $\left[1,2,3\right]$.
 • Adjacent combinations differ by a single index.

Methods

The 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):$

Generate the combinations of four pairs of nested parentheses.

 > $\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}}\mathrm{NearPerfectParentheses}\left(4\right)\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}:$
 1 3 5 7 1 3 5 6 1 3 4 6 1 3 4 5 1 3 4 7 1 2 4 6 1 2 4 5 1 2 4 7 1 2 3 6 1 2 3 4 1 2 3 5 1 2 3 7 1 2 5 6 1 2 5 7

Compute the number of iterations.

 > $\mathrm{Number}\left(\mathrm{NearPerfectParentheses}\left(4\right)\right)$
 ${14}$ (1)

References

 Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 4; generating all trees, sec. 7.2.1.6, generating all trees, algorithm N, near-perfect parentheses, p. 8.

Compatibility

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