 Iterator - Maple Programming Help

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

Iterator

 SetPartitionGrayCode
 generate set partition with restricted growth strings in Gray code order

 Calling Sequence SetPartitionGrayCode(n, opts)

Parameters

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

Options

 • append_change = truefalse
 True means append the index that changed to the Array. The default is false.
 • compile = truefalse
 True means compile the iterator. The default is true.
 • 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 SetPartitionGrayCode command returns an iterator that generates all partitions of a set of integers from one to n. The output consists of the the restricted growth strings of length n in Gray code 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

The 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.
 • ToSets(v): convert the Array v from a restricted growth string to the corresponding list of sets of positive integers.

Examples

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

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

 > $M≔\mathrm{SetPartitionGrayCode}\left(4\right):$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p\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",p\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 0 0 0 1 0 0 1 1 0 0 1 2 0 0 1 0 0 1 1 0 0 1 1 2 0 1 1 1 0 1 2 1 0 1 2 2 0 1 2 3 0 1 2 0 0 1 0 0 0 1 0 2 0 1 0 1

Append the index that changed to the output Array.

 > $M≔\mathrm{SetPartitionGrayCode}\left(4,\mathrm{append_change}\right):$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}p\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",p\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 0 0 0 0 1 4 0 0 1 1 3 0 0 1 2 4 0 0 1 0 4 0 1 1 0 2 0 1 1 2 4 0 1 1 1 4 0 1 2 1 3 0 1 2 2 4 0 1 2 3 4 0 1 2 0 4 0 1 0 0 3 0 1 0 2 4 0 1 0 1 4

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{SetPartitionGrayCode}\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{SetPartitionGrayCode}\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 1 = [{1, 2}, {3, 4}] 0 0 1 2 = [{1, 2}, {3}, {4}] 0 0 1 0 = [{1, 2, 4}, {3}] 0 1 1 0 = [{1, 4}, {2, 3}] 0 1 1 2 = [{1}, {2, 3}, {4}] 0 1 1 1 = [{1}, {2, 3, 4}] 0 1 2 1 = [{1}, {2, 4}, {3}] 0 1 2 2 = [{1}, {2}, {3, 4}] 0 1 2 3 = [{1}, {2}, {3}, {4}] 0 1 2 0 = [{1, 4}, {2}, {3}] 0 1 0 0 = [{1, 3, 4}, {2}] 0 1 0 2 = [{1, 3}, {2}, {4}] 0 1 0 1 = [{1, 3}, {2, 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 E, p. 127, ans. 14.

Compatibility

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