Mixed Radix Tuples - Maple Help

Iterator

Parameters

 radices - list(posint) opts - (optional) equation(s) of the form option = value; specify options for the MixedRadixTuples 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 MixedRadixTuples command returns an iterator that generates all tuples of a mixed-radix number.
 • The radices parameter is a list of positive integers that specify the radices of the number. The k-th integer is the radix at the k-th index.

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.
 • 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 tuples with the radices $\left[2,4,3\right]$.

 > $M≔\mathrm{MixedRadixTuples}\left(\left[2,4,3\right]\right):$
 > $\mathrm{seq}\left(v\left[\right],v=M\right)$
 $\left[\begin{array}{ccc}{0}& {0}& {0}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {0}& {0}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {1}& {0}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {1}& {0}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {2}& {0}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {2}& {0}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {3}& {0}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {3}& {0}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {0}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {0}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {1}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {1}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {2}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {2}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {3}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {3}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {0}& {2}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {0}& {2}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {1}& {2}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {1}& {2}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {2}& {2}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {2}& {2}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {3}& {2}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {3}& {2}\end{array}\right]$ (1)

Compute the number of iterations.

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

Return the element with rank equal to 4.

 > $\mathrm{Unrank}\left(M,4\right)$
 $\left[\begin{array}{ccc}{1}& {1}& {0}\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}{1}& {1}& {0}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {2}& {0}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {2}& {0}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {3}& {0}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {3}& {0}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {0}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {0}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {1}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {1}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {2}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {2}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {3}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {3}& {1}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {0}& {2}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {0}& {2}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {1}& {2}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {1}& {2}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {2}& {2}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {2}& {2}\end{array}\right]{,}\left[\begin{array}{ccc}{0}& {3}& {2}\end{array}\right]{,}\left[\begin{array}{ccc}{1}& {3}& {2}\end{array}\right]$ (4)

Making Change

Given 7 pennies (1-cent coin), 5 nickels (5-cents), 3 dimes (10-cents), and 3 quarters (25-cents), list all ways to change 75 cents.

Assign a procedure that converts a Vector of the number of coins to a string.  The contents of the Vector are the number of pennies, nickels, dimes, and quarters, in that order.

 > Change := proc(V) local i;     sprintf("%d pennies + %d nickels "             "+ %d dimes + %d quarters "             "= 75 cents"             , seq(i, i=V)); end proc:

Assign a predicate that returns true if the Vector V has the exact change.

 > $\mathrm{is_exact}≔V↦\mathrm{evalb}\left(V\left[1\right]+5\cdot V\left[2\right]+10\cdot V\left[3\right]+25\cdot V\left[4\right]=75\right):$

Iterate through all all possibilities, accepting those that are exact, and transforming the Vector to the desired string.

 > $\mathrm{iter}≔\mathrm{MixedRadixTuples}\left(\left[7,5,3,3\right]\right):$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathrm{chng}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathrm{iter}\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}}\mathbf{if}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathrm{is_exact}\left(\mathrm{chng}\right)\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{then}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{printf}\left("%s\n",\mathrm{Change}\left(\mathrm{chng}\right)\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{if}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$
 5 pennies + 4 nickels + 0 dimes + 2 quarters = 75 cents 5 pennies + 2 nickels + 1 dimes + 2 quarters = 75 cents 0 pennies + 3 nickels + 1 dimes + 2 quarters = 75 cents 5 pennies + 0 nickels + 2 dimes + 2 quarters = 75 cents 0 pennies + 1 nickels + 2 dimes + 2 quarters = 75 cents

References

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

Compatibility

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