Iterator - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

Iterator

  

Partition

  

generate partitions of an integer

 

Calling Sequence

Parameters

Options

Description

Examples

References

Compatibility

Calling Sequence

Partition(n, opts)

Parameters

n

-

posint; integer to partition

opts

-

(optional) equation(s) of the form option = value; specify options for the Partition command

Options

• 

compile = truefalse

  

True means compile the iterator. The default is true.

Description

• 

The Partition command returns an iterator that generates all partitions of the integer n, in reverse lexicographic order.

• 

A partition of integer n is a sequence of integers a1&comma;&comma;am such that n&equals;k&equals;1mak and 0<akn for k1&comma;&comma;m.

• 

The n parameter is the integer to partition.

• 

The output of the iterator is an array of fixed length n. The partition is in the indices 1 to lengthP, where P is the assigned iterator.

Methods

The iterator object has the following methods. The self parameter is the iterator object.

• 

length(self): returns the usable length of the iterator Array. The actual length is fixed, but the usable length depends on the iteration.

• 

Number(self): return the number of iterations required to step through the iterator, assuming it started at rank one.

Examples

withIterator&colon;

Iterate through the partitions of 8.

n8&colon;

PPartitionn&colon;

Use the length method of the iterator P to determine the number of elements in each partition.

forpinPdoprintf%d\n&comma;p1..lengthPenddo

8
7 1
6 2
6 1 1
5 3
5 2 1
5 1 1 1
4 4
4 3 1
4 2 2
4 2 1 1
4 1 1 1 1
3 3 2
3 3 1 1
3 2 2 1
3 2 1 1 1
3 1 1 1 1 1
2 2 2 2
2 2 2 1 1
2 2 1 1 1 1
2 1 1 1 1 1 1
1 1 1 1 1 1 1 1

Compute the number of iterations.

NumberP

22

(1)

seqp1..lengthM&comma;p=P

8,7,6,6,5,5,5,4,4,4,4,4,3,3,3,3,3,2,2,2,2,1

(2)

Add the elements of each partition to verify they sum to n.

seqaddpk&comma;k=1..lengthP&comma;p=P

8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8

(3)

References

  

Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 3; generating all combinations and partitions, sec. 7.2.1.4, generating all partitions, algorithm P, partitions in reverse lexicographic order.  The algorithm was corrected; Knuth_errata, p. 38.

Compatibility

• 

The Iterator[Partition] command was introduced in Maple 2016.

• 

For more information on Maple 2016 changes, see Updates in Maple 2016.

See Also

combinat[numbpart]

Iterator

Iterator[MultiPartition]

Iterator[PartitionFixedSize]

Iterator[SetPartitions]