Partitions

Partition{T<:IntegerUnion} <: AbstractVector{T}

A partition of a non-negative integer $n$ is a decreasing sequence $λ₁ ≥ λ₂ ≥ … ≥ λᵣ$ of positive integers $λᵢ$ such that $n = λ₁ + … + λᵣ$. The $λᵢ$ are called the parts of the partition and $r$ is called the length.

A partition can be encoded as an array with elements $λᵢ$. We provide the parametric type Partition{T} which is a subtype of AbstractVector{T} where T can be any subtype of IntegerUnion. All functions that can be used for vectors (1-dimensional arrays) can thus be used for partitions as well. There is no performance impact by using an own type for partitions rather than simply using arrays. The parametric type allows to increase performance by using smaller integer types. For efficiency, the Partition constructor does not check whether the given array is indeed a decreasing sequence.

Examples

A partition can be created by either calling Partition on an array of integers or by calling Partition with arguments being the sequence of parts.

julia> P = Partition([6,4,4,2]) #The partition 6+4+4+2 of 16.
[6, 4, 4, 2]

julia> P = Partition(6,4,4,2) #Same as above but less to type
[6, 4, 4, 2]

julia> length(P)
4

julia> P[1]
6

Usually, $|λ| ≔ n$ is called the size of $λ$. In Julia, the function size for arrays already exists and returns the dimension of an array. Instead, you can use the Julia function sum to get the sum of the parts.

julia> P = Partition(6,4,4,2)
[6, 4, 4, 2]

julia> sum(P) 
16

You can create partitions with smaller integer types as follows.

julia> P = Partition{Int8}(6,4,4,2) #Or Partition(Int8[6,4,4,2])
Int8[6, 4, 4, 2]

There is a unique partition of 0, namely the empty partition (of length 0). It can be created as follows.

julia> P = Partition() #Or Partition([])
Int64[]
julia> sum(P)
0
julia> length(P)
0
julia> P = Partition{Int8}() #Or Partition(Int8[])
Int8[]

References

1. William Fulton (1997)
2. Donald E. Knuth (2011), Section 7.2.1.4 (starting on page 390).

getindex_safe(P::Partition, i::IntegerUnion)

In algorithms involving partitions it is sometimes convenient to be able to access parts beyond the length of the partition and then one wants to get the value zero instead of an error. This function is a shortcut for

return (i>length(P.p) ? 0 : getindex(P.p,i))

If you are sure that P[i] exists, use getindex because this will be faster.

Examples

julia> P=Partition([3,2,1])
[3, 2, 1]

julia> getindex_safe(P, 3)
1

julia> getindex_safe(P, 4)
0

partitions(n::IntegerUnion)

A list of all partitions of a non-negative integer n, produced in lexicographically descending order. This ordering is like in Sage, but opposite to GAP. You can apply the function reverse to reverse the order. As usual, you may increase performance by using smaller integer types.

Algorithm

The algorithm used is "Algorithm ZS1" by A. Zoghbi, I. Stojmenovic (1998). This algorithm is also discussed in Donald E. Knuth (2011), Algorithm P (page 392).

Examples

julia> partitions(4) # Use partitions(Int8(4)) to use 8-bit integers
5-element Vector{Partition{Int64}}:
 [4]
 [3, 1]
 [2, 2]
 [2, 1, 1]
 [1, 1, 1, 1]

num_partitions(n::IntegerUnion)

The number of integer partitions of the non-negative integer n.

Examples

julia> num_partitions(1000)
24061467864032622473692149727991

Algorithm

We use the function arith_number_of_partitions from W. B. Hart (2010) which is very fast. It is based on the Hardy-Ramanujan-Rademacher formula, see Fredrik Johansson (2012) for details.

Further references

1. Donald E. Knuth (2011), Section 7.2.1.4 (starting on page 395).
2. OEIS Foundation Inc. (2023), A000041

partitions(m::T, n::IntegerUnion, l1::IntegerUnion, l2::IntegerUnion; only_distinct_parts::Bool = false) where T <: IntegerUnion

A list of all partitions of a non-negative integer m into n >= 0 parts with lower bound l1 >= 0 and upper bound l2 for the parts. There are two choices for the parameter only_distinct_parts:

• false: no further restriction (default);
• true: only distinct parts. The partitions are produced in decreasing order.

Examples

We compute all partitions of 7 into 3 parts where all parts are between 1 and 4:

julia> partitions(7, 3, 1, 4)
3-element Vector{Partition{Int64}}:
 [4, 2, 1]
 [3, 3, 1]
 [3, 2, 2]

Same as above but requiring all parts to be distinct:

julia> partitions(7, 3, 1, 4 ; only_distinct_parts=true)
1-element Vector{Partition{Int64}}:
 [4, 2, 1]

Algorithm

The algorithm used is "parta" in W. Riha, K. R. James (1976), de-gotoed from old ALGOL 60 code by E. Thiel.

partitions(m::T, n::IntegerUnion) where T<:IntegerUnion

All partitions of a non-negative integer m into n parts (no further restrictions).

Examples

# All partitions of 7 into 3 parts.
julia> partitions(7, 3)
4-element Vector{Partition{Int64}}:
 [5, 1, 1]
 [4, 2, 1]
 [3, 3, 1]
 [3, 2, 2]

Algorithm

This function is a shortcut for partitions(m,n,1,m;only_distinct_parts=false).

num_partitions(n::IntegerUnion, k::IntegerUnion)

The number of integer partitions of the non-negative integer n into k >= 0 parts.

Algorithm

We use the recurrence relation $p_k(n) = p_{k-1}(n-1) + p_k(n-k)$, where $p_k(n)$ denotes the number of partitions of $n$ into $k$ parts; see Donald E. Knuth (2011), Section 7.2.1.4, Equation (39) on page 399.

References

1. OEIS Foundation Inc. (2023), A008284

partitions(m::T, n::IntegerUnion, v::Vector{T}, mu::Vector{S}) where {T<:IntegerUnion, S<:IntegerUnion}

All partitions of a non-negative integer m into n >= 0 parts, where each part is an element in the vector v of positive integers and each v[i] occurs a maximum of mu[i] > 0 times. We assume (without loss of generality) that the entries in v are strictly increasing. The partitions are produced in lexicographically decreasing order.

Examples

We compute the partitions of 100 into seven parts, where the parts are required to be elements from {1, 2, 5, 10, 20, 50} and each part is allowed to occur at most twice.

julia> partitions(100, 7, [1,2,5,10,20,50], [2,2,2,2,2,2])
1-element Vector{Partition{Int64}}:
 [50, 20, 20, 5, 2, 2, 1]

Algorithm

The algorithm used is "partb" in W. Riha, K. R. James (1976), de-gotoed from old ALGOL 60 code by E. Thiel. The algorithm as published in the paper has several issues and we hope to have fixed them all, see the code for details. Some initial fixing was done by T. Schmit.

partitions(m::T, v::Vector{T}, mu::Vector{S}) where {T<:IntegerUnion,S<:IntegerUnion}

All partitions of a non-negative integer m where each part is an element in the vector v of positive integers and each v[i] occurs a maximum of mu[i] > 0 times. We assume (without loss of generality) that the entries in v are strictly increasing.

Example

We compute all partitions of 100 where the parts are from {1, 2, 5, 10, 20, 50} and each part is allowed to occur at most twice:

julia> partitions(100, [1,2,5,10,20,50], [2,2,2,2,2,2])
6-element Vector{Partition{Int64}}:
 [50, 50]
 [50, 20, 20, 10]
 [50, 20, 20, 5, 5]
 [50, 20, 10, 10, 5, 5]
 [50, 20, 20, 5, 2, 2, 1]
 [50, 20, 10, 10, 5, 2, 2, 1]

Algorithm

We use the function partitions(m,n,v,mu), looping over the number of possible parts of partitions.

function partitions(m::T, v::Vector{T}) where T<:IntegerUnion

All partitions of a non-negative integer m where each part is an element in the vector v. We assume (without loss of generality) that the entries in v are strictly increasing.

Example

We compute the number of partitions of 100 where the parts are from {1, 2, 5, 10, 20, 50}:

julia> length(partitions(100, [1,2,5,10,20,50]))
4562

Algorithm

We use the function partitions(m,n,v,mu), looping over the number of possible parts of partitions.

conjugate(lambda::Partition{T}) where T<:IntegerUnion

The conjugate of a partition is obtained by considering its Young diagram (see Tableaux) and then flipping it along its main diagonal.

Examples

julia> conjugate(Partition(8,8,8,7,2,1,1))
[7, 5, 4, 4, 4, 4, 4, 3]

References

1. William Fulton (1997), page 2
2. Donald E. Knuth (2011), Section 7.2.1.4, page 394.

dominates(lambda::Partition, mu::Partition)

The dominance order on partitions is the partial order $⊵$ defined by $λ ⊵ μ$ if and only if $λ₁ + … + λᵢ ≥ μ₁ + … + μᵢ$ for all i. If $λ ⊵ μ$ one says that $λ$ dominates $μ$. This function returns true if and only if lambda dominates mu.

Note that whereas the lexicographic ordering is a total ordering, the dominance ordering is not.

Examples

julia> dominates( Partition(3,1), Partition(2,2) )
true

julia> dominates( Partition(4,1), Partition(3,3) )
false

Remarks

Donald E. Knuth (2011) says majorizes instead of dominates and uses the symbol $⪰$ instead of $⊵$.

References

1. William Fulton (1997), page 26
2. Donald E. Knuth (2011), Section 7.2.1.4, Exercise 54 (page 412)