Iterator - Maple Programming Help

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

Iterator

 CartesianProduct
 generate a Cartesian product of lists and sets

 Calling Sequence CartesianProduct(L, opts)

Parameters

 L - seq({list,set}); lists and sets opts - (optional) equation(s) of the form option = value; specify options for the CartesianProduct 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 CartesianProduct command returns an iterator that generates the Cartesian product of a sequence of lists and sets. The k-th element of the output Array contains an element from the k-th set/list in the input.
 • The L parameter is a sequence of lists and sets. For efficiency, each list/set must have at least two elements, otherwise an error is raised.
 • Internally this iterator uses a loopless, reflected, mixed-radix Gray code for the iterator; see MixedRadixGrayCode.

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.
 • Unrank(self,rnk): return a one-dimensional Array corresponding to the iterator output with rank rnk.

Examples

 > $\mathrm{with}\left(\mathrm{Iterator}\right):$

Construct an iterator that generates the Cartesian product of a list and two sets.

 > $M≔\mathrm{CartesianProduct}\left(\left[1,2,2\right],\left\{a,b\right\},\left\{c,d,e\right\}\right):$

Step through, and print, the elements one-by-one.

 > $\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("%\left\{\right\}a\n",v\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}$
 1 a c 2 a c 2 a c 2 b c 2 b c 1 b c 1 b d 2 b d 2 b d 2 a d 2 a d 1 a d 1 a e 2 a e 2 a e 2 b e 2 b e 1 b e

Generate the entire sequence.

 > $\mathrm{seq}\left(v\left[\right],v=M\right)$
 $\left[\begin{array}{ccc}{1}& {a}& {c}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {a}& {c}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {a}& {c}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {b}& {c}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {b}& {c}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {b}& {c}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {b}& {d}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {b}& {d}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {b}& {d}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {a}& {d}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {a}& {d}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {a}& {d}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {a}& {e}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {a}& {e}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {a}& {e}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {b}& {e}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {b}& {e}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {b}& {e}\end{array}\right]$ (1)

Compute the number of iterations.

 > $\mathrm{Number}\left(M\right)$
 ${18}$ (2)

Return the element with rank equal to 4.

 > $\mathrm{Unrank}\left(M,4\right)$
 $\left[\begin{array}{ccc}{2}& {b}& {c}\end{array}\right]$ (3)

 > $N≔\mathrm{Object}\left(M,\mathrm{rank}=4\right):$
 > $\mathrm{seq}\left(v\left[\right],v=N\right)$
 $\left[\begin{array}{ccc}{2}& {b}& {c}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {b}& {c}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {b}& {c}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {b}& {d}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {b}& {d}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {b}& {d}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {a}& {d}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {a}& {d}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {a}& {d}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {a}& {e}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {a}& {e}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {a}& {e}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {b}& {e}\end{array}\right]{,}\left[\begin{array}{ccc}{2}& {b}& {e}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {b}& {e}\end{array}\right]$ (4)

References

 Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 2; generating all tuples and permutations, sec. 7.2.1.1, Generating all n-tuples, algorithm  H, loopless reflected mixed-radix Gray generation, p. 20.

Compatibility

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