Multiset partitions

Multiset_partition{T}

Multiset-partitions are generalizations of partitions. An r-component multiset-partition of an integer $n$ is a multiset(a set where each element can be contained multiple times) of partitions $λ¹, λ², …, λʳ$ where each $λⁱ$ is a partition of some integer $nᵢ ≥ 1$ and the $nᵢ$ sum to $n$. As for partitions, we have implemented an own type Multiset_partition{T}. As with partitions, you can can use smaller integer types to increase performance.

Example

julia> P = Multiset_partition( [2,1], [4], [3,2,1] )
{[2, 1], [4], [3, 2, 1]}
julia> sum(P)
13
julia> Multiset_partition( Array{Int8,1}[[2,1], [4], [3,2,1]] ) #Using 8-bit integers
{Int8[2, 1], Int8[4], Int8[3, 2, 1]}

Since Multiset-partitions are unordered sets, you can't call an explicit element, however, you can iterate over a Multiset_partition.

Example

julia> MSP = Multiset_partition( [2,1], [4], [3,2,1] )
{[2, 1], [4], [3, 2, 1]}
julia> for p in MSP println(p) end
[2, 1]
[4]
[3, 2, 1]

multiset_partitions(n::T) where T<:Integer

A list of all multiset_partitions of an integer $n ⋝ 0$.

The performance will suffer by casting $n$ into a smaller integer type, e.g.

multiset_partitions(Int8(20))

multiset_partitions(p::Partition{T})	where T<:Integer

A list of all possible multiset_partitions of a Partition, by regrouping its parts into Partitions.

The algorithm used is the algorithm M by , "The Art of Computer Programming - Volume 4A, Combinatorial Algorithms, Part 1" by Donald E. Knuth(2011), 429–430. De-gotoed, index-shifted and generalized.

multiset_partitions(n::T, r::Integer) where T<:Integer

A list of all multiset_partitions of an integer $n ⋝ 0$ into $r ⋝ 1$ parts.

multiset_partitions(p::Partition{T}, r::Integer) where T<:Integer

A list of all possible $r$-restricted multiset_partitions of a Partition, by regrouping its parts into Partitions.

The algorithm used is a version of the algorithm M by , "The Art of Computer Programming - Volume 4A, Combinatorial Algorithms, Part 1" by Donald E. Knuth, 429–430 http://www.cs.utsa.edu/~wagner/knuth/fasc3b.pdf. De-gotoed, index-shifted and generalized.