Iterator - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim


Overview of the Iterator Package

 

Calling Sequence

Description

Examples

Compatibility

Calling Sequence

Iterator:-command(arguments)

command(arguments)

Description

• 

The Iterator package exports constructors of efficient iterators over discrete structures.

• 

Each iterator is an object with a ModuleIterator method. It can be used in for loops and in seq, add, or mul commands.

• 

To reduce memory usage the iterators use a mutable data structure, a one-dimensional Array, as the output.

• 

All constructors provide a compile option that is true by default.  When true, the returned iterator is compiled.

• 

Because these iterators use the state of the object, using the same iterator in independent loops is not allowed; an error is raised if that occurs.  To loop over the the same discrete structure in independent loops, copy the object (use Object).

• 

See Iterator/Details for details of an iterator object.

All Commands

The following commands are available.

BinaryGrayCode

BinaryTrees

BoundedComposition

CartesianProduct

Chase

Combination

Composition

DeBruijn

FillRucksack

LyndonWord

MixedRadixGrayCode

MixedRadixTuples

MultiCombination

MultiPartition

MultiSeq

NearPerfectParentheses

Necklace

NestedParentheses

OrientedForests

Partition

PartitionFixedSize

PartitionPartCount

Permute

Prenecklace

Product

RevolvingDoorCombination

SetPartitionFixedSize

SetPartitionGrayCode

SetPartitions

SplitRanks

TopologicalSorts

WeightedComposition

Subpackages

The following subpackages are available.

Inversion

procedures for converting between permutations and inversion tables

MixedRadix

procedures for operating on mixed-radix tuples

Trees

procedure for converting between tree representations

Combinations

BoundedComposition

generate bounded compositions that sum to a constant

Chase

generate all (s,t)-combinations of zeros and ones in near-perfect order

Combination

generate t-combinations of a set

FillRucksack

generate feasible ways to fill a rucksack

MultiCombination

generate multicombinations

RevolvingDoorCombination

generate combinations in the lexicographic revolving-door Gray code

Compositions

Composition

generate compositions of an integer

WeightedComposition

generate weighted compositions that sum to a constant

Counters

MixedRadixTuples

generate mixed-radix tuples

MultiSeq

generate multiple sequences

Conversions

Inversion

subpackage for converting between permutations and inversion tables

Trees

subpackage for converting between tree representations

Gray Codes

BinaryGrayCode

generate n-bit binary Gray code

Chase

generate all (s,t)-combinations of zeros and ones in near-perfect order

MixedRadixGrayCode

generate a mixed-radix Gray code

RevolvingDoorCombinations

generate combinations in the lexicographic revolving-door Gray code

Necklaces

DeBruijn

generate Lyndon words that form a de Bruijn sequence

LyndonWord

generate Lyndon words

Necklace

generate necklaces

Prenecklace

generate prenecklaces

Parentheses

NearPerfectParentheses

generate positions of left-parentheses in pairs of nested parentheses

NestedParentheses

generate pairs of nested parentheses

Partitions

MultiPartition

generate partitions of a multiset

Partition

generate all partitions of an integer

PartitionFixedSize

generate fixed-size partitions of an integer

PartitionPartCount

generate partitions of an integer in part-count form

Permutations

Permute

generate permutations of a list

TopologicalSorts

generate permutations with restrictions

Products

CartesianProduct

generate a Cartesian product of lists and sets

Product

create the product of iterators

Set Partitions

SetPartitionFixedSize

generate fixed-size partitions of a set

SetPartitionGrayCode

generate set partitions with restricted growth strings in Gray code order

SetPartitions

generate set partitions with restricted growth strings

Support

SplitRanks

compute the starting ranks and iterations suitable for parallelizing an iterator

Trees

BinaryTrees

generate binary trees of a given size

OrientedForests

generate oriented forests of a given size

Trees

subpackage for converting between tree representations

The Twelve-Fold Way

• 

Richard Stanley, in Enumerative Combinatorics, categorizes common combinatorial selections using the cardinality of unrestricted, injective, and surjective functions between discrete domains in a 4×3 tableau called "The Twelve-fold Way." The following table reproduces this categorization, using the enumeration of ways to place balls into urns, and links to the appropriate iterator.

balls per urn

unrestricted

at most 1

at least 1

n labeled balls, m labeled urns

MixedRadixTuples([m$n])

Permute(m,n)

[1]

n unlabeled balls, m labeled urns

Multicombination([n$m],n)

Combination(m,n)

Composition(n,parts=m)

n labeled balls, m unlabeled urns

SetPartitions(n,maxparts=m)

[2]

SetPartitions(n,parts=m)

n unlabeled balls, m unlabeled urns

PartitionFixedSize(n,maxparts=m)

[2]

PartitionFixedSize(n,parts=m)

• 

[1] Partitions of n distinct objects into m ordered parts.

• 

[2] If nm there is one arrangement that satisfies this, otherwise none.

Example Index

• 

Index of interesting examples. The link goes to the help page; look in its Examples section for the example.

Alphametic

solve an alphametic puzzle (cryptarithm)

Contingency tables

compute number of contingency tables

Dudney's century puzzle

solve Dudney's century puzzle

Matrix permanent

compute matrix permanent with Ryser's algorithm

Poker rank

compute number of distinct ranks of a poker hand

Simplified Dudney's century puzzle

solve simplified Dudney's century puzzle

Split list of floats

split a list of floating-point numbers into nearly equal sublists.  Demonstrates the creation and use of parallelized iterators.

Young rectangle

create a Young rectangle (specialization of a Young tableau)

Examples

withIterator:

Use Permute to construct an iterator over all permutations of the list [1,2,2,3].

PPermute1,2,2,3:

Use a for-loop to iterate over the permutations.

forpinPdoprintf%d ,pend do

1 2 2 3
1 2 3 2
1 3 2 2
2 1 2 3
2 1 3 2
2 2 1 3
2 2 3 1
2 3 1 2
2 3 2 1
3 1 2 2
3 2 1 2
3 2 2 1

The same output is more conveniently generated with the Print method. Here the number of iterations is limited and showrank option is used to display the rank.

PrintP,10,'showrank':

 1: 1 2 2 3
 2: 1 2 3 2
 3: 1 3 2 2
 4: 2 1 2 3
 5: 2 1 3 2
 6: 2 2 1 3
 7: 2 2 3 1
 8: 2 3 1 2
 9: 2 3 2 1
10: 3 1 2 2

Use a seq command to create the entire sequence.

seqp[],p=P

1223,1232,1322,2123,2132,2213,2231,2312,2321,3122,3212,3221

(1)

Note the use of the square brackets, [], to instantiate the Vector that is assigned to p.  Without them, all values in the final expression sequence equal the last value because the p' evaluates to the Vector rather than its content.  Here is what happens when the square brackets are omitted.

seqp,p=P

1223,1223,1223,1223,1223,1223,1223,1223,1223,1223,1223,1223

(2)

Using hasNext and getNext

• 

Use Combination to generate all triplets of the integers 0 to 4. Extract the two procedures, hasNext and getNext, from the ModuleIterator method of the iterator object and use them in a while-loop.

MCombination5,3:

hasNext,getNextModuleIteratorM:

whilehasNextdoprintgetNextend do

012

013

023

123

014

024

124

034

134

234

(3)

Concurrent iterators

Construct an iterator over the 2-permutations of the list 1,1,2, use Object to create an identical, but independent, second iterator, and use both iterators in a dual-loop.

PPermute1,1,2,2:

QObjectP:

forpinPdoforqinQdoprintp,qend doend do:

11,11

11,12

11,21

12,11

12,12

12,21

21,11

21,12

21,21

(4)

Compatibility

• 

The Iterator package was introduced in Maple 2016.

• 

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

See Also

combinat

combstruct

Iterator/Details