Iterator - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

Iterator

  

MultiPartition

  

generate partitions of a multiset

 

Calling Sequence

Parameters

Options

Description

Examples

References

Compatibility

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, 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 non-zero columns, starting from the first, is given by the length method.

Examples

withIterator:

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

Construct the iterator.

MMultiPartition2,3:

Print the partitions.

forminMdoprintf%{}d\n\n,m..,1..lengthMenddo:

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.

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

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

See Also

Iterator

Iterator[Partition]