Iterator - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

Iterator

  

NestedParentheses

  

generate pairs of nested parentheses

 

Calling Sequence

Parameters

Options

Description

Examples

References

Compatibility

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

withIterator:

MNestedParentheses4:

forVinMdoprintf%d\n,Venddo:

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.

NumberM

14

(1)

Return the element with rank equal to 4.

UnrankM,4

01001011

(2)

Copy the iterator, but start with rank equal to 4.

NObjectM,rank=4:

seqv,v=N

01001011,01000111,00110101,00110011,00101101,00101011,00100111,00011101,00011011,00010111,00001111

(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.

str1StringNestedParentheses15,rank=106

str1Iterator:-NestedParentheses(15,('rank') = 1000000)

(4)

Check the result by iterating a million times - 1.

iterNestedParentheses15:

cnt1:

forViniterwhilecnt<1061docntcnt+1enddo&colon;

str2Stringiter

str2Iterator:-NestedParentheses(15)

(5)

evalbstr1=str2

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.

• 

For more information on Maple 2016 changes, see Updates in Maple 2016.

See Also

Iterator

Iterator[NearPerfectParentheses]