Iterator - Maple Programming Help

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

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.

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 partitions.

 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}m\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}M\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{printf}\left("%\left\{\right\}d\n\n",m\left[..,1..\mathrm{length}\left(M\right)\right]\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}:$
 2 3 2 0 2 1 2 0 1 2 2 0 0 1 1 1 2 0 0 3 2 0 0 0 2 1 2 0 0 0 0 1 1 1 1 1 3 0 1 1 2 1 1 1 0 2 0 1 1 1 0 1 1 1 1 1 0 1 0 2 1 1 0 0 1 0 1 1 1 1 0 0 0 3 1 1 0 0 0 0 2 1 1 1 0 0 0 0 0 1 1 1

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.