|
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
|
|
|
True means compile the iterator. The default is true.
|
|
Specify the starting rank of the iterator. The default is one. Passing a value greater than one causes the iterator to skip the lower ranks; this can be useful when parallelizing iterators. 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
|
|
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.
|
•
|
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
|
|
>
|
|
>
|
|
1: 0 1 0 1 0 1 0 1
2: 0 1 0 1 0 0 1 1
3: 0 1 0 0 1 1 0 1
4: 0 1 0 0 1 0 1 1
5: 0 1 0 0 0 1 1 1
6: 0 0 1 1 0 1 0 1
7: 0 0 1 1 0 0 1 1
8: 0 0 1 0 1 1 0 1
9: 0 0 1 0 1 0 1 1
10: 0 0 1 0 0 1 1 1
11: 0 0 0 1 1 1 0 1
12: 0 0 0 1 1 0 1 1
13: 0 0 0 1 0 1 1 1
14: 0 0 0 0 1 1 1 1
| |
Compute the number of iterations.
Return the element with rank equal to 4.
Copy the iterator, but start with rank equal to 4.
>
|
|
| (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.
>
|
|
| (4) |
Check the result by iterating a million times - 1.
>
|
|
>
|
|
| (5) |
|
|
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.
|
|
|
|