SetPartitions - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Iterator

 SetPartitions
 generate set partitions with restricted growth strings

 Calling Sequence SetPartitions(n, opts)

Parameters

 n - nonnegint; size of set to partition opts - (optional) equation(s) of the form option = value; specify options for the SetPartitions command

Options

 • compile = truefalse
 True means compile the iterator. The default is true.
 • maxparts = nonnegint
 Specifies the maximum number of parts in each partition. The default is n.
 • parts = integer
 Specifies the number of parts in each partition. A value less than zero is ignored. The default is -1, which is ignored.
 • rank = nonnegint
 Specify the starting rank of the iterator. The default is one. Passing a value greater than one causes the iterator to skip the lower ranks; this can be useful when parallelizing iterators. The starting rank reverts to one when the iterator is reset, reused, or copied.

Description

 • The SetPartitions command returns an iterator that generates partitions of a set of integers from one to n. The output consists of the restricted growth strings of length n in lexicographic order.
 • A restricted growth string of length n corresponds to a partition of the set of integers 1 to n. Each integer in the output Array designates the set to which the index belongs; the sets are numbered starting at 0. For example, $⟨0,0,1,2⟩$ corresponds to the partition $\left\{1,2\right\},\left\{3\right\},\left\{4\right\}$.

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.
 • Rank(self,L): return the rank of the current iteration. Optionally pass L, a list or one-dimensional rtable, and return its rank.
 • ToSets(v): convert the Array v from a restricted growth string to the corresponding list of sets of positive integers.
 • Unrank(self,rnk): return a one-dimensional Array corresponding to the iterator output with rank rnk.

Examples

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

Iterate through all partitions of $\left\{1,2,3,4\right\}$.

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

Iterate through partitions with at most 3 parts.

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

Iterate through partitions with exactly 2 parts.

 > $N≔\mathrm{Object}\left(M,'\mathrm{parts}'=2\right):$
 > $\mathrm{Print}\left(N,'\mathrm{showrank}'\right):$
 1: 0 0 0 1 2: 0 0 1 0 3: 0 0 1 1 4: 0 1 0 0 5: 0 1 0 1 6: 0 1 1 0 7: 0 1 1 1

Compute the number of iterations.

 > $\mathrm{Number}\left(M\right)$
 ${15}$ (1)

Mapping of restricted growth strings to partitions

Print the correspondence between the restricted growth strings and the actual partitions.  Use the ToSets method to do the conversion.

 > $M≔\mathrm{SetPartitions}\left(4\right):$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}V\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{SetPartitions}\left(4\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathrm{printf}\left("%d = %a",V,M:-\mathrm{ToSets}\left(V\right)\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{end do}:$
 0 0 0 0 = [{1, 2, 3, 4}] 0 0 0 1 = [{1, 2, 3}, {4}] 0 0 1 0 = [{1, 2, 4}, {3}] 0 0 1 1 = [{1, 2}, {3, 4}] 0 0 1 2 = [{1, 2}, {3}, {4}] 0 1 0 0 = [{1, 3, 4}, {2}] 0 1 0 1 = [{1, 3}, {2, 4}] 0 1 0 2 = [{1, 3}, {2}, {4}] 0 1 1 0 = [{1, 4}, {2, 3}] 0 1 1 1 = [{1}, {2, 3, 4}] 0 1 1 2 = [{1}, {2, 3}, {4}] 0 1 2 0 = [{1, 4}, {2}, {3}] 0 1 2 1 = [{1}, {2, 4}, {3}] 0 1 2 2 = [{1}, {2}, {3, 4}] 0 1 2 3 = [{1}, {2}, {3}, {4}]

References

 Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 3; generating all combinations and partitions, sec. 7.2.1.5, generating all set partitions, algorithm H, restricted growth strings in lexicographic order, pp. 62-63 and p. 124 ex. 1.

Compatibility

 • The Iterator[SetPartitions] command was introduced in Maple 2016.
 • For more information on Maple 2016 changes, see Updates in Maple 2016.
 • The Iterator[SetPartitions] command was updated in Maple 2022.
 • The n parameter was updated in Maple 2022.
 • The maxparts and parts options were updated in Maple 2022.