Multi Partition - Maple Help

Iterator

 MultiPartition
 generate partitions of a multiset

 Calling Sequence MultiPartition(N, opts)

Parameters

 N - list(posint); multiplicities of elements opts - (optional) equation(s) of the form option = value; specify options for the MultiPartition command

Options

 • compile = truefalse
 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 positive integers, $\left[{m}_{1},\dots ,{m}_{n}\right]$, specifying the multiplicity of the distinct elements in the multiset.
 • The iterator returns an Array, $W$, with ${W}_{i,j}$ being the multiplicity of the i-th element in the j-th part of a partition. The number of non-zero columns, starting from the first, is given by the length method.
 • This iterator object has the common iterator methods.

Examples

 > $\mathrm{with}\left(\mathrm{Iterator}\right):$

Create all partitions of a multiset containing two elements, one occurs twice, the other three times.

Construct the iterator.

 > $M≔\mathrm{MultiPartition}\left(\left[2,3\right]\right):$

Print the first five partitions.

 > $\mathrm{Print}\left(M,5,'\mathrm{showrank}'\right):$
 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.

 > $\mathrm{Factorizations}\left(144\right)$
 $\left[\left[{144}\right]{,}\left[{3}{,}{48}\right]{,}\left[{9}{,}{16}\right]{,}\left[{3}{,}{3}{,}{16}\right]{,}\left[{2}{,}{72}\right]{,}\left[{6}{,}{24}\right]{,}\left[{2}{,}{3}{,}{24}\right]{,}\left[{8}{,}{18}\right]{,}\left[{3}{,}{6}{,}{8}\right]{,}\left[{2}{,}{8}{,}{9}\right]{,}\left[{2}{,}{3}{,}{3}{,}{8}\right]{,}\left[{4}{,}{36}\right]{,}\left[{2}{,}{2}{,}{36}\right]{,}\left[{12}{,}{12}\right]{,}\left[{3}{,}{4}{,}{12}\right]{,}\left[{2}{,}{6}{,}{12}\right]{,}\left[{2}{,}{2}{,}{3}{,}{12}\right]{,}\left[{4}{,}{4}{,}{9}\right]{,}\left[{3}{,}{3}{,}{4}{,}{4}\right]{,}\left[{2}{,}{4}{,}{18}\right]{,}\left[{4}{,}{6}{,}{6}\right]{,}\left[{2}{,}{3}{,}{4}{,}{6}\right]{,}\left[{2}{,}{2}{,}{4}{,}{9}\right]{,}\left[{2}{,}{2}{,}{3}{,}{3}{,}{4}\right]{,}\left[{2}{,}{2}{,}{2}{,}{18}\right]{,}\left[{2}{,}{2}{,}{6}{,}{6}\right]{,}\left[{2}{,}{2}{,}{2}{,}{3}{,}{6}\right]{,}\left[{2}{,}{2}{,}{2}{,}{2}{,}{9}\right]{,}\left[{2}{,}{2}{,}{2}{,}{2}{,}{3}{,}{3}\right]\right]$ (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.
 • For more information on Maple 2016 changes, see Updates in Maple 2016.