Iterator
MultiPartition
generate partitions of a multiset
Calling Sequence
Parameters
Options
Description
Examples
References
Compatibility
MultiPartition(N, opts)
N
-
list(nonnegint); multiplicities of elements
opts
(optional) equation(s) of the form option = value; specify options for the MultiPartition command
compile = truefalse
True means compile the iterator. The default is true.
The MultiPartition command returns an iterator that generates all partitions of a multiset. A multiset is a generalization of a set; members are allowed to appear more than once.
The N parameter specifies the multiset to partition. It is a list of nonnegative integers, m1,…,mn, specifying the multiplicity of the distinct elements in the multiset.
The iterator returns an Array, W, with Wi,j being the multiplicity of the i-th element in the j-th part of a partition. The number of nonzero columns, starting from the first, is given by the length method.
This iterator object has the common iterator methods.
withIterator:
Create all partitions of a multiset containing two elements, one occurs twice, the other three times.
Construct the iterator.
M≔MultiPartition2,3:
Print the first five partitions.
PrintM,5,showrank:
1: 2 3 2: 2 0 2 1 3: 2 0 1 2 4: 2 0 0 1 1 1 5: 2 0 0 3
Integer Factorizations
Generating all factorizations of an integer, given its prime factorization, is equivalent to generating all partitions of the multiset of prime factors. Here we assign a procedure that returns an iterator that generates each factorization.
Factorizations := proc(n :: posint) local F,L,M,N,T,num; # Factor n into a multiset format. L := op(2, ifactors(n)); F := map2(op,1,L); # prime factors N := map2(op,2,L); # exponents num := numelems(L); # number of prime factors # Assign a procedure that converts the Array output # to a list of factors T := proc(m) sort([seq(mul(F[i]^m[i,j],i=1..num), j=1..length(M))]); end proc: # Construct the iterator, then iterate through it. M := Iterator:-MultiPartition(N); [seq(T(m), m = M)]; end proc:
Generate all factorizations of 144.
Factorizations144
144,3,48,9,16,3,3,16,2,72,6,24,2,3,24,8,18,3,6,8,2,8,9,2,3,3,8,4,36,2,2,36,12,12,3,4,12,2,6,12,2,2,3,12,4,4,9,3,3,4,4,2,4,18,4,6,6,2,3,4,6,2,2,4,9,2,2,3,3,4,2,2,2,18,2,2,6,6,2,2,2,3,6,2,2,2,2,9,2,2,2,2,3,3
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 M, multipartitions in decreasing lexicographic order, pp. 75-76. The algorithm was corrected; Knuth_errata, p. 75.
The Iterator[MultiPartition] command was introduced in Maple 2016.
For more information on Maple 2016 changes, see Updates in Maple 2016.
The Iterator[MultiPartition] command was updated in Maple 2022.
The N parameter was updated in Maple 2022.
See Also
Iterator[Partition]
Download Help Document
