Iterator - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

Parameters

Options

Description

Examples

References

Compatibility

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 1,2,3,4.

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

withIterator:

Iterate through the partitions of 1,2,3,4.

MSetPartitionGrayCode4:

forpinMdoprintf%d\n,penddo

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.

MSetPartitionGrayCode4,append_change:

forpinMdoprintf%d\n,penddo

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.

NumberM

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.

MSetPartitionGrayCode4:

forVinSetPartitionGrayCode4doprintf%d = %a\n,V,M:-ToSetsVenddo:

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.

See Also

Iterator

Iterator[SetPartitionFixedSize]

Iterator[SetPartitions]