Set Partition Gray Code - Maple Help

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 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

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.
 • 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):$
 > $\mathrm{Print}\left(M,'\mathrm{showrank}'\right):$
 1: 0 0 0 0  2: 0 0 0 1  3: 0 0 1 1  4: 0 0 1 2  5: 0 0 1 0  6: 0 1 1 0  7: 0 1 1 2  8: 0 1 1 1  9: 0 1 2 1 10: 0 1 2 2 11: 0 1 2 3 12: 0 1 2 0 13: 0 1 0 0 14: 0 1 0 2 15: 0 1 0 1

Append the index that changed to the output Array.

 > $M≔\mathrm{SetPartitionGrayCode}\left(4,'\mathrm{append_change}'\right):$
 > $\mathrm{Print}\left(M,'\mathrm{showrank}'\right):$
 1: 0 0 0 0  2: 0 0 0 1  3: 0 0 1 1  4: 0 0 1 2  5: 0 0 1 0  6: 0 1 1 0  7: 0 1 1 2  8: 0 1 1 1  9: 0 1 2 1 10: 0 1 2 2 11: 0 1 2 3 12: 0 1 2 0 13: 0 1 0 0 14: 0 1 0 2 15: 0 1 0 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{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.
 • For more information on Maple 2016 changes, see Updates in Maple 2016.