Composition - Maple Help

Iterator

 Composition
 generate compositions of an integer

 Calling Sequence Composition(n, opts)

Parameters

 n - posint; integer to compose, must be greater than one opts - (optional) equation(s) of the form option = value; specify options for the Composition command

Options

 • compile = truefalse
 True means compile the iterator. The default is true.
 • maxparts = posint
 Specifies the maximum number of integers in each composition. The default is n.
 • parts = nonnegint
 Specifies the number of integers in each composition. Must be either 0 (the default) or greater than one and less than or equal to n. The default, 0, is ignored. A non-zero value cannot be used with the maxparts option.

Description

 • The Composition command returns an iterator that generates all compositions of the integer n.
 • A composition of integer n is a sequence of positive integers that sum to n.
 • The n parameter is the integer to decompose.  It must be greater than one.
 • The output of the iterator is an array of fixed length n. The composition 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 compositions of 5.

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

Compute the number of iterations.

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

Add the parts of each composition 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)$
 ${5}{,}{5}{,}{5}{,}{5}{,}{5}{,}{5}{,}{5}{,}{5}{,}{5}{,}{5}{,}{5}{,}{5}{,}{5}{,}{5}{,}{5}{,}{5}$ (2)

References

 Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 2; generating all tuples and permutations, sec. 7.2.1.1, generating all n-tuples, algorithm A, p. 77, answer 12.

Compatibility

 • The Iterator[Composition] command was introduced in Maple 2021.