Iterator - Maple Programming Help

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

Iterator

 Partition
 generate partitions of an integer

 Calling Sequence Partition(n, opts)

Parameters

 n - posint; integer to partition opts - (optional) equation(s) of the form option = value; specify options for the Partition command

Options

 • compile = truefalse
 True means compile the iterator. The default is true.

Description

 • The Partition command returns an iterator that generates all partitions of the integer n, in reverse lexicographic order.
 • A partition of integer n is a sequence of integers $\left({a}_{1},\dots ,{a}_{m}\right)$ such that $n=\sum _{k=1}^{m}{a}_{k}$ and $0<{a}_{k}\le n$ for $k\in \left\{1,\dots ,m\right\}$.
 • The n parameter is the integer to partition.
 • The output of the iterator is an array of fixed length n. The partition is in the indices 1 to $\mathrm{length}\left(P\right)$, where P is the assigned iterator.

Methods

The iterator object has the following methods. The self parameter is the iterator object.

 • length(self): returns the usable length of the iterator Array. The actual length is fixed, but the usable length depends on the iteration.
 • Number(self): return the number of iterations required to step through the iterator, assuming it started at rank one.

Examples

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

Iterate through the partitions of 8.

 > $n≔8:$
 > $P≔\mathrm{Partition}\left(n\right):$

Use the length method of the iterator P to determine the number of elements in each partition.

 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}P\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("%d\n",p\left[1..\mathrm{length}\left(P\right)\right]\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}$
 8 7 1 6 2 6 1 1 5 3 5 2 1 5 1 1 1 4 4 4 3 1 4 2 2 4 2 1 1 4 1 1 1 1 3 3 2 3 3 1 1 3 2 2 1 3 2 1 1 1 3 1 1 1 1 1 2 2 2 2 2 2 2 1 1 2 2 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Compute the number of iterations.

 > $\mathrm{Number}\left(P\right)$
 ${22}$ (1)
 > $\mathrm{seq}\left(p\left[1..\mathrm{length}\left(M\right)\right],p=P\right)$
 $\left[\begin{array}{c}{8}\end{array}\right]{,}\left[\begin{array}{c}{7}\end{array}\right]{,}\left[\begin{array}{c}{6}\end{array}\right]{,}\left[\begin{array}{c}{6}\end{array}\right]{,}\left[\begin{array}{c}{5}\end{array}\right]{,}\left[\begin{array}{c}{5}\end{array}\right]{,}\left[\begin{array}{c}{5}\end{array}\right]{,}\left[\begin{array}{c}{4}\end{array}\right]{,}\left[\begin{array}{c}{4}\end{array}\right]{,}\left[\begin{array}{c}{4}\end{array}\right]{,}\left[\begin{array}{c}{4}\end{array}\right]{,}\left[\begin{array}{c}{4}\end{array}\right]{,}\left[\begin{array}{c}{3}\end{array}\right]{,}\left[\begin{array}{c}{3}\end{array}\right]{,}\left[\begin{array}{c}{3}\end{array}\right]{,}\left[\begin{array}{c}{3}\end{array}\right]{,}\left[\begin{array}{c}{3}\end{array}\right]{,}\left[\begin{array}{c}{2}\end{array}\right]{,}\left[\begin{array}{c}{2}\end{array}\right]{,}\left[\begin{array}{c}{2}\end{array}\right]{,}\left[\begin{array}{c}{2}\end{array}\right]{,}\left[\begin{array}{c}{1}\end{array}\right]$ (2)

Add the elements of each partition to verify they sum to n.

 > $\mathrm{seq}\left(\mathrm{add}\left(p\left[k\right],k=1..\mathrm{length}\left(P\right)\right),p=P\right)$
 ${8}{,}{8}{,}{8}{,}{8}{,}{8}{,}{8}{,}{8}{,}{8}{,}{8}{,}{8}{,}{8}{,}{8}{,}{8}{,}{8}{,}{8}{,}{8}{,}{8}{,}{8}{,}{8}{,}{8}{,}{8}{,}{8}$ (3)

References

 Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 3; generating all combinations and partitions, sec. 7.2.1.4, generating all partitions, algorithm P, partitions in reverse lexicographic order.  The algorithm was corrected; Knuth_errata, p. 38.

Compatibility

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