Overview - Maple Help

All Products Maple MapleSim

Home : Support : Online Help : Mathematics : Discrete Mathematics : Combinatorics : Iterator : Overview

Overview of the Iterator Package

	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 \times 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 $n \leq m$ 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

>	$with (Iterator) &colon;$

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

>	$P ≔ Permute ([1, 2, 2, 3]) &colon;$

Use a for-loop to iterate over the permutations.

>	$for p in P do printf (%d\n, p) end 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.

>	$Print (P, 10,'showrank') &colon;$

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.

>	$seq (p [], p = P)$

$[\begin{array}{c} 1 & 2 & 2 & 3 \end{array}], [\begin{array}{c} 1 & 2 & 3 & 2 \end{array}], [\begin{array}{c} 1 & 3 & 2 & 2 \end{array}], [\begin{array}{c} 2 & 1 & 2 & 3 \end{array}], [\begin{array}{c} 2 & 1 & 3 & 2 \end{array}], [\begin{array}{c} 2 & 2 & 1 & 3 \end{array}], [\begin{array}{c} 2 & 2 & 3 & 1 \end{array}], [\begin{array}{c} 2 & 3 & 1 & 2 \end{array}], [\begin{array}{c} 2 & 3 & 2 & 1 \end{array}], [\begin{array}{c} 3 & 1 & 2 & 2 \end{array}], [\begin{array}{c} 3 & 2 & 1 & 2 \end{array}], [\begin{array}{c} 3 & 2 & 2 & 1 \end{array}]$

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

>	$seq (p, p = P)$

$[\begin{array}{c} 1 & 2 & 2 & 3 \end{array}], [\begin{array}{c} 1 & 2 & 2 & 3 \end{array}], [\begin{array}{c} 1 & 2 & 2 & 3 \end{array}], [\begin{array}{c} 1 & 2 & 2 & 3 \end{array}], [\begin{array}{c} 1 & 2 & 2 & 3 \end{array}], [\begin{array}{c} 1 & 2 & 2 & 3 \end{array}], [\begin{array}{c} 1 & 2 & 2 & 3 \end{array}], [\begin{array}{c} 1 & 2 & 2 & 3 \end{array}], [\begin{array}{c} 1 & 2 & 2 & 3 \end{array}], [\begin{array}{c} 1 & 2 & 2 & 3 \end{array}], [\begin{array}{c} 1 & 2 & 2 & 3 \end{array}], [\begin{array}{c} 1 & 2 & 2 & 3 \end{array}]$

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

>	$M ≔ Combination (5, 3) &colon;$

>	$hasNext, getNext ≔ ModuleIterator (M) &colon;$

>	$while hasNext () do print (getNext ()) end do$

$[\begin{array}{c} 0 & 1 & 2 \end{array}]$

$[\begin{array}{c} 0 & 1 & 3 \end{array}]$

$[\begin{array}{c} 0 & 2 & 3 \end{array}]$

$[\begin{array}{c} 1 & 2 & 3 \end{array}]$

$[\begin{array}{c} 0 & 1 & 4 \end{array}]$

$[\begin{array}{c} 0 & 2 & 4 \end{array}]$

$[\begin{array}{c} 1 & 2 & 4 \end{array}]$

$[\begin{array}{c} 0 & 3 & 4 \end{array}]$

$[\begin{array}{c} 1 & 3 & 4 \end{array}]$

$[\begin{array}{c} 2 & 3 & 4 \end{array}]$

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

>	$P ≔ Permute ([1, 1, 2], 2) &colon;$

>	$Q ≔ Object (P) &colon;$

>	$for p in P do for q in Q do print (p, q) end do end do &colon;$

$[\begin{array}{c} 1 & 1 \end{array}], [\begin{array}{c} 1 & 1 \end{array}]$

$[\begin{array}{c} 1 & 1 \end{array}], [\begin{array}{c} 1 & 2 \end{array}]$

$[\begin{array}{c} 1 & 1 \end{array}], [\begin{array}{c} 2 & 1 \end{array}]$

$[\begin{array}{c} 1 & 2 \end{array}], [\begin{array}{c} 1 & 1 \end{array}]$

$[\begin{array}{c} 1 & 2 \end{array}], [\begin{array}{c} 1 & 2 \end{array}]$

$[\begin{array}{c} 1 & 2 \end{array}], [\begin{array}{c} 2 & 1 \end{array}]$

$[\begin{array}{c} 2 & 1 \end{array}], [\begin{array}{c} 1 & 1 \end{array}]$

$[\begin{array}{c} 2 & 1 \end{array}], [\begin{array}{c} 1 & 2 \end{array}]$

$[\begin{array}{c} 2 & 1 \end{array}], [\begin{array}{c} 2 & 1 \end{array}]$

(4)

Compatibility

•	The Iterator package was introduced in Maple 2016.

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

Maple

Maple Add-Ons

MapleSim

MapleSim Add-Ons

Systems Engineering

Consulting Services

Maple T.A. and Möbius

Education

Industries

Automotive and Aerospace

Robotics

Machine Design & Industrial Automation

Other

Application Areas

Product Pricing

Purchasing

Institutional Student Licensing

Maplesoft Elite Maintenance (EMP)

Support

Product Training

Online Product Help

Webinars & Events

Publications

Content Hubs

Examples & Applications

Community

About Maplesoft

Media Center

User Community

Contact

Online Help

All Products Maple MapleSim

Maple

Powerful math software that is easy to use

Maple Add-Ons

MapleSim

Advanced System Level Modeling

MapleSim Add-Ons

Systems Engineering

Consulting Services

Maple T.A. and Möbius

Education

Industries

Automotive and Aerospace

Robotics

Machine Design & Industrial Automation

Other

Application Areas

Product Pricing

Purchasing

Institutional Student Licensing

Maplesoft Elite Maintenance (EMP)

Support

Product Training

Online Product Help

Webinars & Events

Publications

Content Hubs

Examples & Applications

Community

About Maplesoft

Media Center

User Community

Contact

Online Help

All Products Maple MapleSim