Partition - Maple Help

Iterator

 Partition
 generate all 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

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.

Examples

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

Iterate through the partitions of 8.

 > $n≔8:$
 > $P≔\mathrm{Partition}\left(n\right):$
 > $\mathrm{Print}\left(P,'\mathrm{showrank}'\right):$
 1: 8  2: 7 1  3: 6 2  4: 6 1 1  5: 5 3  6: 5 2 1  7: 5 1 1 1  8: 4 4  9: 4 3 1 10: 4 2 2 11: 4 2 1 1 12: 4 1 1 1 1 13: 3 3 2 14: 3 3 1 1 15: 3 2 2 1 16: 3 2 1 1 1 17: 3 1 1 1 1 1 18: 2 2 2 2 19: 2 2 2 1 1 20: 2 2 1 1 1 1 21: 2 1 1 1 1 1 1 22: 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.