Partition - Maple Help

Iterator

 Partition
 generate all partitions of an integer

 Calling Sequence Partition(n, m, opts)

Parameters

 n - posint; integer to partition m - (optional) posint; maximum integer in a 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}_{k}\right)$ such that $n=\sum _{j=1}^{k}{a}_{j}$ and $0<{a}_{j}\le n$ for $j\in \left\{1,\dots ,k\right\}$.
 • The n parameter is the integer to partition.
 • The optional m parameter is the maximum integer that can appear in any partition. The default is n.
 • 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.

 > $P≔\mathrm{Partition}\left(8\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

Iterate through the partitions of 8, with maximum integer 5.

 > $P≔\mathrm{Partition}\left(8,5\right):$
 > $\mathrm{Print}\left(P,'\mathrm{showrank}'\right):$
 1: 5 3  2: 5 2 1  3: 5 1 1 1  4: 4 4  5: 4 3 1  6: 4 2 2  7: 4 2 1 1  8: 4 1 1 1 1  9: 3 3 2 10: 3 3 1 1 11: 3 2 2 1 12: 3 2 1 1 1 13: 3 1 1 1 1 1 14: 2 2 2 2 15: 2 2 2 1 1 16: 2 2 1 1 1 1 17: 2 1 1 1 1 1 1 18: 1 1 1 1 1 1 1 1

Compute the number of iterations.

 > $\mathrm{Number}\left(P\right)$
 ${18}$ (1)

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

 > $\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}$ (2)

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.