 Iterator - Maple Programming Help

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

Iterator

 PartitionFixedSize
 generate fixed-size partitions of an integer

 Calling Sequence PartitionFixedSize(n, m, opts)

Parameters

 n - posint; integer to partition m - integer[2..n]; number of partitions opts - (optional) equation(s) of the form option = value; specify options for the PartitionFixedSize command

Options

 • 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. It must be lie in the range $2..n$.

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. , 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,5\right):$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}V\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}M\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",V\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$
 8 1 1 1 1 7 2 1 1 1 6 3 1 1 1 5 4 1 1 1 6 2 2 1 1 5 3 2 1 1 4 4 2 1 1 4 3 3 1 1 5 2 2 2 1 4 3 2 2 1 3 3 3 2 1 4 2 2 2 2 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.

Compatibility

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