Iterator - Maple Programming Help

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

Iterator

 NestedParentheses
 generate pairs of nested parentheses

 Calling Sequence NestedParentheses(n,opts)

Parameters

 n - nonnegint; number of pairs of parentheses opts - (optional) equation(s) of the form option = value; specify options for the NestedParentheses command

Options

 • compile = truefalse
 True means compile the iterator. The default is true.
 • rank = nonnegint
 Specify the starting rank of the iterator. The default is one. The starting rank reverts to one when the iterator is reset, reused, or copied.

Description

 • The NestedParentheses command returns an iterator that generates all nested n-pairs of parentheses.
 • A left parenthesis is represented by 0, a right parenthesis by 1.
 • The n parameter specifies the number of pairs of parentheses in the output.

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.
 • Rank(self,L): return the rank of the current iteration. Optionally pass L, a list or one-dimensional rtable, and return its rank.
 • String(self,opts) : return a string corresponding to the current value of the iterator. The keyword options left and right are strings that replace the 0's and 1's in the Array. The default values for left and right are the strings ( and ), respectively.
 • Unrank(self,rnk): return a one-dimensional Array corresponding to the iterator output with rank rnk.
 • See Iterator[Trees] for procedures to convert this format (A) to other formats for nested parentheses and binary trees.

Examples

 > $\mathrm{with}\left(\mathrm{Iterator}\right):$
 > $M≔\mathrm{NestedParentheses}\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 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 1 0 0 1 1 1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 1

Compute the number of iterations.

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

Return the element with rank equal to 4.

 > $\mathrm{Unrank}\left(M,4\right)$
 $\left[\begin{array}{cccccccc}{0}& {1}& {0}& {0}& {1}& {0}& {1}& {1}\end{array}\right]$ (2)

 > $N≔\mathrm{Object}\left(M,\mathrm{rank}=4\right):$
 > $\mathrm{seq}\left(v\left[\right],v=N\right)$
 $\left[\begin{array}{cccccccc}{0}& {1}& {0}& {0}& {1}& {0}& {1}& {1}\end{array}\right]{,}\left[\begin{array}{cccccccc}{0}& {1}& {0}& {0}& {0}& {1}& {1}& {1}\end{array}\right]{,}\left[\begin{array}{cccccccc}{0}& {0}& {1}& {1}& {0}& {1}& {0}& {1}\end{array}\right]{,}\left[\begin{array}{cccccccc}{0}& {0}& {1}& {1}& {0}& {0}& {1}& {1}\end{array}\right]{,}\left[\begin{array}{cccccccc}{0}& {0}& {1}& {0}& {1}& {1}& {0}& {1}\end{array}\right]{,}\left[\begin{array}{cccccccc}{0}& {0}& {1}& {0}& {1}& {0}& {1}& {1}\end{array}\right]{,}\left[\begin{array}{cccccccc}{0}& {0}& {1}& {0}& {0}& {1}& {1}& {1}\end{array}\right]{,}\left[\begin{array}{cccccccc}{0}& {0}& {0}& {1}& {1}& {1}& {0}& {1}\end{array}\right]{,}\left[\begin{array}{cccccccc}{0}& {0}& {0}& {1}& {1}& {0}& {1}& {1}\end{array}\right]{,}\left[\begin{array}{cccccccc}{0}& {0}& {0}& {1}& {0}& {1}& {1}& {1}\end{array}\right]{,}\left[\begin{array}{cccccccc}{0}& {0}& {0}& {0}& {1}& {1}& {1}& {1}\end{array}\right]$ (3)

Compute the millionth iteration of 15 nested pairs of parentheses. Initialize an iterator with rank equal to one million, then use the String method to return the corresponding string.

 > $\mathrm{str1}≔\mathrm{String}\left(\mathrm{NestedParentheses}\left(15,\mathrm{rank}={10}^{6}\right)\right)$
 ${\mathrm{str1}}{≔}{"Iterator:-NestedParentheses\left(15,\left(\text{'}rank\text{'}\right) = 1000000\right)"}$ (4)

Check the result by iterating a million times - 1.

 > $\mathrm{iter}≔\mathrm{NestedParentheses}\left(15\right):$
 > $\mathrm{cnt}≔1:$
 > $\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{iter}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{while}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathrm{cnt}<{10}^{6}-1\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{cnt}≔\mathrm{cnt}+1\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$
 > $\mathrm{str2}≔\mathrm{String}\left(\mathrm{iter}\right)$
 ${\mathrm{str2}}{≔}{"Iterator:-NestedParentheses\left(15\right)"}$ (5)
 > $\mathrm{evalb}\left(\mathrm{str1}=\mathrm{str2}\right)$
 ${\mathrm{false}}$ (6)

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 P, nested parentheses in lexicographic order, p. 5.
 ibid, Algorithm U, unrank a string of nested parentheses, p. 14.

Compatibility

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