PartitionFixedSize - Maple Help

Iterator

 PartitionFixedSize
 generate some partitions of an integer

 Calling Sequence PartitionFixedSize(n, m, opts)

Parameters

 n - nonnegint; integer to partition m - (optional) nonnegint; number of parts opts - (optional) equation(s) of the form option = value; specify options for the PartitionFixedSize command

Options

 • maxparts = nonnegint
 Specifies the maximum number of parts in each partition. Must be either 0 or greater than one. The default, 0, is ignored. When maxparts is used, some of the elements in the output may be zero.
 • parts = nonnegint
 Specifies the number of parts in each partition. This option overrides the positional argument m; the default is m.
 • compile = truefalse
 True means compile the iterator. The default is true.

Description

 • The PartitionFixedSize command returns an iterator that generates all integer m-tuples, ${a}_{1},\dots ,{a}_{m}$ such that ${a}_{k}\ge {a}_{k+1}$, ${a}_{m}\ge 1$, and ${\sum }_{k=1}^{m}{a}_{k}=n$.
 • The partitions are visited in colex order, that is, the reflected sequence ${a}_{m},\dots ,{a}_{1}$ is in lexicographic order.
 • The n parameter specifies the integer to partition.
 • The m parameter specifies the size of the partition. The option parts may also be used to specify the number of parts.

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.

Notes

 • The cost to run completely through this iterator is at most $\mathrm{O}\left(3N\left(n,m\right)+m\right)$, where $N\left(n,m\right)$ is the number of partitions of $n$ of size $m$, cf. [1], theorem H, p. 50.

Examples

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

Construct an iterator to generate all 5-partitions of 12.

 > $M≔\mathrm{PartitionFixedSize}\left(12,'\mathrm{parts}'=5\right):$
 > $\mathrm{Print}\left(M,'\mathrm{showrank}'\right):$
 1: 8 1 1 1 1  2: 7 2 1 1 1  3: 6 3 1 1 1  4: 5 4 1 1 1  5: 6 2 2 1 1  6: 5 3 2 1 1  7: 4 4 2 1 1  8: 4 3 3 1 1  9: 5 2 2 2 1 10: 4 3 2 2 1 11: 3 3 3 2 1 12: 4 2 2 2 2 13: 3 3 2 2 2

Extend the iterator to generate all partitions of 5 or less.

 > $N≔\mathrm{Object}\left(M,'\mathrm{maxparts}'=5\right):$
 > $\mathrm{Print}\left(N,'\mathrm{showrank}'\right):$
 1: 12 0 0 0 0  2: 11 1 0 0 0  3: 10 2 0 0 0  4: 9 3 0 0 0  5: 8 4 0 0 0  6: 7 5 0 0 0  7: 6 6 0 0 0  8: 10 1 1 0 0  9: 9 2 1 0 0 10: 8 3 1 0 0 11: 7 4 1 0 0 12: 6 5 1 0 0 13: 8 2 2 0 0 14: 7 3 2 0 0 15: 6 4 2 0 0 16: 5 5 2 0 0 17: 6 3 3 0 0 18: 5 4 3 0 0 19: 4 4 4 0 0 20: 9 1 1 1 0 21: 8 2 1 1 0 22: 7 3 1 1 0 23: 6 4 1 1 0 24: 5 5 1 1 0 25: 7 2 2 1 0 26: 6 3 2 1 0 27: 5 4 2 1 0 28: 5 3 3 1 0 29: 4 4 3 1 0 30: 6 2 2 2 0 31: 5 3 2 2 0 32: 4 4 2 2 0 33: 4 3 3 2 0 34: 3 3 3 3 0 35: 8 1 1 1 1 36: 7 2 1 1 1 37: 6 3 1 1 1 38: 5 4 1 1 1 39: 6 2 2 1 1 40: 5 3 2 1 1 41: 4 4 2 1 1 42: 4 3 3 1 1 43: 5 2 2 2 1 44: 4 3 2 2 1 45: 3 3 3 2 1 46: 4 2 2 2 2 47: 3 3 2 2 2

References

 1. 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 H, partitions into m parts, p. 38, and p. 110, answer 2.

Compatibility

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