Set Partitions - Maple Help

Iterator

 SetPartitions
 generate set partitions with restricted growth strings

 Calling Sequence SetPartitions(n, opts)

Parameters

 n - posint; 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 = posint
 Specifies the maximum number of parts in each partition. Must be greater than one and less than or equal to n. The default is n.
 • parts = nonnegint
 Specifies the number of parts in each partition. 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.
 • rank = nonnegint
 Specify the starting rank of the iterator. The default is one. 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.3em}{0.0ex}}V\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathrm{SetPartitions}\left(4\right)\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 = %a\n",V,M:-\mathrm{ToSets}\left(V\right)\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{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.