|
Calling Sequence
|
|
MultiPartition(N, opts)
|
|
|
Parameters
|
|
|
N
|
-
|
list(nonnegint); multiplicities of elements
|
|
opts
|
-
|
(optional) equation(s) of the form option = value; specify options for the MultiPartition command
|
|
|
|
|
|
Options
|
|
|
|
True means compile the iterator. The default is true.
|
|
|
|
Description
|
|
|
•
|
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, , specifying the multiplicity of the distinct elements in the multiset.
|
|
•
|
The iterator returns an Array, , with 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.
|
|
|
|
Examples
|
|
Create all partitions of a multiset containing two elements, one occurs twice, the other three times.
Construct the iterator.
|
>
|
|
Print the first five partitions.
|
>
|
|
|
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.
|
| (1) |
|
|
|
|
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 M, multipartitions in decreasing lexicographic order, pp. 75-76. The algorithm was corrected; Knuth_errata, p. 75.
|
|
|
|
Compatibility
|
|
|
•
|
The Iterator[MultiPartition] command was introduced in Maple 2016.
|
|
•
|
The Iterator[MultiPartition] command was updated in Maple 2022.
|
|
•
|
The N parameter was updated in Maple 2022.
|
|
|
|
