Partitions

A partition of a non-negative integer $n$ is a decreasing sequence $\lambda_1 \geq \lambda_2\geq \dots \geq \lambda_r$ of positive integers $\lambda_i$ such that $n = \lambda_1 + \dots + \lambda_r$. The $\lambda_i$ are called the parts of the partition and $r$ is called the length. General references on partitions are [Ful97] and [Knu11], Section 7.2.1.4.

A partition can be encoded as an array with elements $\lambda_i$. In OSCAR, the parametric type Partition{T} is provided which is a subtype of AbstractVector{T}. Here, T can be any subtype of IntegerUnion. 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.

partition — Function

partition([T::Type{<:IntegerUnion}], parts::IntegerUnion...; check::Bool = true)
partition(parts::Vector{T}; check::Bool = true) where T <: IntegerUnion

Return the partition given by the integer sequence parts as an object of type Partition{T}.

The element type T may be optionally specified, see also the examples below.

If check is true (default), it is checked whether the given sequence defines a partition.

Examples

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) # the same partition
[6, 4, 4, 2]

julia> P = partition(Int8, 6, 4, 4, 2) # save the elements in 8-bit integers
Int8[6, 4, 4, 2]

source

Because Partition is a subtype of AbstractVector, all functions that can be used for vectors (1-dimensional arrays) can be used for partitions as well.

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

julia> length(P)
4

julia> P[1]
6

However, usually, $|\lambda| := n$ is called the size of $\lambda$. In Julia, the function size for arrays already exists and returns the dimension of an array. Instead, one 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

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. For this, OSCAR provides the function getindex_safe:

getindex_safe — Function

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

Return P[i] if i < length(P) and 0 otherwise. It is assumed that i is positive.

Examples

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

julia> getindex_safe(P, 3)
1

julia> getindex_safe(P, 4)
0

source

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

Generating and counting

partitions — Method

partitions(n::IntegerUnion)

Return an iterator over all partitions of a non-negative integer n, produced in lexicographically descending order. Using a smaller integer type for n (e.g. Int8) may increase performance.

The algorithm used is "Algorithm ZS1" by [ZS98]. This algorithm is also discussed in [Knu11], Algorithm P (page 392).

Examples

julia> p = partitions(4);

julia> first(p)
[4]

julia> collect(p)
5-element Vector{Partition{Int64}}:
 [4]
 [3, 1]
 [2, 2]
 [2, 1, 1]
 [1, 1, 1, 1]

julia> collect(partitions(Int8(4))) # using less memory
5-element Vector{Partition{Int8}}:
 Int8[4]
 Int8[3, 1]
 Int8[2, 2]
 Int8[2, 1, 1]
 Int8[1, 1, 1, 1]

source

number_of_partitions — Method

number_of_partitions(n::IntegerUnion)

Return the number of integer partitions of n. For n < 0, return 0.

Examples

julia> number_of_partitions(1000)
24061467864032622473692149727991

source

For counting partitions, the Hardy-Ramanujan-Rademachen formula is used, see [Joh12] for details. See also [Knu11], Section 7.2.1.4 and [OEIS], A000041.

Partitions with restrictions

How many ways are there to pay one euro, using coins worth 1, 2, 5, 10, 20, 50, and/or 100 cents? What if you are allowed to use at most two of each coin?

This is Exercise 11 in [Knu11], Section 7.2.1.4. It goes back to the famous "Ways to change one dollar" problem, see [Pol56]. Generally, the problem is to generate and/or count partitions satisfying some restrictions. Of course, one could generate the list of all partitions of 100 (there are about 190 million) and then filter the result by the restrictions. But for certain types of restrictions there are much more efficient algorithms. The functions in this section implement some of these. In combination with Julia's filter function one can also handle more general types of restrictions.

For example, there are precisely six ways for the second question in the exercise quoted above:

julia> collect(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]

and there are 4562 ways for the first question in the exercise:

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

The original "Ways to change one dollar" problem has 292 solutions:

julia> length(collect(partitions(100, [1, 5, 10, 25, 50])))
292

number_of_partitions — Method

number_of_partitions(n::IntegerUnion, k::IntegerUnion)

Return the number of integer partitions of the non-negative integer n into k >= 0 parts. If n < 0 or k < 0, return 0.

source

For counting the partitions the recurrence relation $p_k(n) = p_{k - 1}(n - 1) + p_k(n - k)$ is used, where $p_k(n)$ denotes the number of partitions of $n$ into $k$ parts; see [Knu11], Section 7.2.1.4, Equation (39), and also [OEIS], A008284.

partitions — Method

partitions(n::IntegerUnion, k::IntegerUnion; only_distinct_parts::Bool = false)
partitions(n::IntegerUnion, k::IntegerUnion, lb::IntegerUnion, ub::IntegerUnion; only_distinct_parts::Bool = false)

Return an iterator over all partitions of a non-negative integer n into k >= 0 parts. Optionally, a lower bound lb >= 0 and an upper bound ub for the parts can be supplied. In this case, the partitions are produced in decreasing order.

There are two choices for the parameter only_distinct_parts:

false: no further restriction (default);
true: only distinct parts.

The implemented algorithm is "parta" in [RJ76].

Examples

All partitions of 7 into 3 parts:

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

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

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

source

partitions — Method

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

Return an iterator over all partitions of a non-negative integer n where each part is an element in the vector v of positive integers. It is assumed that the entries in v are strictly increasing.

If the optional vector mu is supplied, then each v[i] occurs a maximum of mu[i] > 0 times per partition.

If the optional integer k >= 0 is supplied, the partitions will be into k parts. In this case, the partitions are produced in lexicographically decreasing order.

The implemented algorithm is "partb" in [RJ76].

Example

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

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

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> collect(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]

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> collect(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]

source

Operations

The conjugate of a partition $\lambda$ is obtained by considering its Young diagram (see Tableaux) and then flipping it along its main diagonal, see [Ful97], page 2, and [Knu11], Section 7.2.1.4.

conjugate — Function

conjugate(lambda::Partition)

Return the conjugate of the partition lambda.

Examples

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

source

Relations

The dominance order on partitions is the partial order $\trianglerighteq$ defined by $\lambda \trianglerighteq\mu$ if and only if $\lambda_1 + \dots + \lambda_i \geq \mu_1 + \dots + \mu_i$ for all $i$. If $\lambda\trianglerighteq\mu$ one says that $\lambda$ dominates $\mu$. See [Ful97], page 26, and [Knu11], Section 7.2.1.4, Exercise 54.

Note that whereas the lexicographic ordering is a total ordering, the dominance ordering is not. Further, [Knu11] says majorizes instead of dominates and uses the symbol $\succeq$ instead of $\trianglerighteq$.

dominates — Function

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

Return true if lambda dominates mu, false otherwise.

Examples

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

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

source