Partitions

Partition{T} <: AbstractArray{T,1}

A partition of an integer n ≥ 0 is a decreasing sequence λ=(λ₁,…,λᵣ) of positive integers λᵢ whose sum is equal to n. The λᵢ are called the parts of the partition. We encode a partition as an array with elements λᵢ. You may increase performance by using smaller integer types, see the examples below. For efficiency, the Partition constructor does not check whether the given array is in fact a partition, i.e. a decreasing sequence.

Examples

julia> P=Partition([3,2,1]) #The partition 3+2+1 of 6
[3, 2, 1]
julia> sum(P) #The sum of the parts.
6
julia> P[1] #First component
3
julia> P=Partition(Int8[3,2,1]) #Same partition but using 8 bit integers

Remarks

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

• There is no performance impact by using an own type for partitions rather than simply using arrays—and this is of course much cleaner. The implementation of a subtype of AbstractArray is explained in the Julia documentation.

References

1. Wikipedia, Partition (number theory)

partitions(n::Integer)

A list of all partitions of an integer n ≥ 0, 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. The algorithm used is "Algorithm ZS1" by Zoghbi & Stojmenovic (1998).

Examples

julia> partitions(Int8(10)) #Using 8-bit integers

References

1. Zoghbi, A. & Stojmenovic, I. (1998). Fast algorithms for generating integer partitions. Int. J. Comput. Math., 70(2), 319–332. https://doi.org/10.1080/00207169808804755

num_partitions(n::Integer)
num_partitions(n::fmpz)

The number of integer partitions of the integer n ≥ 0. Uses the function from FLINT, which is very fast.

References

1. The On-Line Encyclopedia of Integer Sequences, A000041
2. FLINT, Number of partitions

ascending_partitions(n::Integer;alg="ks")

Instead of encoding a partition of an integer n ≥ 0 as a descending sequence (which is our convention), one can also encode it as an ascending sequence. In the papers Kelleher & O'Sullivan (2014) and Merca (2012) it is said that generating the list of all ascending partitions is more efficient than generating descending ones. To test this, I have implemented the algorithms given in the papers:

1. "ks" (default) is the algorithm "AccelAsc" (Algorithm 4.1) in Kelleher & O'Sullivan (2014).
2. "m" is Algorithm 6 in Merca (2012). This is actually similar to "ks".

The ascending partitions are stored here as arrays and are not of type Partition since the latter are descending by our convention. I am using "ks" as default since it looks slicker and I believe there is a tiny mistake in the publication of "m" (which I fixed).

Comparison

I don't see a significant speed difference to the descending encoding:

julia> @btime partitions(Int8(90));
    3.376 s (56634200 allocations: 6.24 GiB)

julia> @btime ascending_partitions(Int8(90),alg="ks");
    3.395 s (56634200 allocations: 6.24 GiB)

julia> @btime ascending_partitions(Int8(90),alg="m");
    3.451 s (56634200 allocations: 6.24 GiB)

References

1. Kelleher, J. & B., O'Sullivan (2014). Generating All Partitions: A Comparison Of Two Encodings. arXiv:0909.2331v2. https://arxiv.org/abs/0909.2331

2. Merca, M. (2012). Fast algorithm for generating ascending compositions. J. Math. Model. Algorithms, 11(1), 89–104. https://doi.org/10.1007/s10852-011-9168-y

partitions(m::Integer, n::Integer, l1::Integer, l2::Integer; z=0)

A list of all partitions of an integer m ≥ 0 into n ≥ 0 parts with lower bound l1 ≥ 0 and upper bound l2 ≥ l1 for the parts. There are two choices for the parameter z:

• z=0: no further restriction (default);
• z=1: only distinct parts.

The partitions are produced in decreasing order.

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

References

1. Riha, W. & James, K. R. (1976). Algorithm 29 efficient algorithms for doubly and multiply restricted partitions. Computing, 16, 163–168. https://link.springer.com/article/10.1007/BF02241987

partitions(m::Integer, n::Integer)

All partitions of an integer m ≥ 0 into n ≥ 1 parts (no further restrictions).

num_partitions(n::Integer, k::Integer)
num_partitions(n::fmpz, k::fmpz)

The number of integer partitions of the integer n ≥ 0 into k ≥ 0 parts. The implementation uses a recurrence relation.

References

1. The On-Line Encyclopedia of Integer Sequences, A008284

partitions(mu::Array{Integer,1}, m::Integer, v::Array{Integer,1}, n::Integer)

All partitions of an integer m >= 0 into n >= 1 parts, where each part is an element in v and each v[i] occurs a maximum of mu[i] times. The partitions are produced in decreasing order. The algorithm used is a de-gotoed version (by E. Thiel!) of algorithm "partb" in Riha & James (1976).

Remark

The original algorithm lead to BoundsErrors, since r could get smaller than 1. Furthermore x and y are handled as arrays with an infinite length. After finding all valid partitions, the algorithm will continue searching for partitions of length n+1. We thus had to add a few additional checks and interruptions. Done by T. Schmit.

References

1. Riha, W. & James, K. R. (1976). Algorithm 29 efficient algorithms for doubly and multiply restricted partitions. Computing, 16, 163–168. https://link.springer.com/article/10.1007/BF02241987

conjugate(λ::Partition{T}) where T<:Integer

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

References

1. Wikipedia, Partition (number theory)

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

In algorithms involving partitions it is sometimes convenient to be able to access parts beyond the length of the partition, and then you want to get 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.

dominates(λ::Partition, μ::Partition)

The dominance order on partitions is the partial order ⊵ defined by λ ⊵ μ if and only if λ₁ + … + λᵢ ≥ μ₁ + … + μᵢ for all i. This function returns true if λ ⊵ μ.

References

1. Wikipedia, Dominance order