Integer partitions

Posted on 05 June, 2021

Algorithms for integer partitions.

Table of contents

  1. Introduction
  2. Recursion
    1. Counting
    2. Integer partitions
    3. Bounded partitions
  3. Linear
    1. Integer partitions
    2. Bounded partitions

Introduction

As per Wikipedia, an integer partition of $n$ is the number of ways of writing $n$ as a positive integer. For example, for 5:

\[\begin{align} &5\\ &4+1\\ &3+2\\ &3+1+1\\ &2+2+1\\ &2+1+1+1\\ &1+1+1+1+1 \end{align}\]

For this post I’ll look at slight variation where a maximum value can be set. In that case, some of the combinations need to be excluded. For example for $n=5$ and a maximum value of $3$, the top two ways are excluded.

The previous blog post The Birthday Problem: Advanced required something a little more complicated: integer partitions but bounded by certain values at each index. For example, select 5 people from 3 teams where there are 2 people in the first team, 1 person in the second team, and 5 or more people in the third team. Here the partitions are:

\[\begin{align} &2+1+2\\ &2+0+3\\ &1+1+3\\ &1+0+4\\ &0+1+4\\ &0+0+5 \end{align}\]

Note that in this problem permutations are distinct from each other, unlike the first problem.

The rest of this post will detail algorithms for these in Julia code.

Recursion

Counting

Define $p(n)$ as the count of integer partitions of $n$. Then $p(n) = \sum_{k=1}^n p(n - k)$. This can readily be converted into a recursive formula:

function count_integer_partitions(n::Integer, max_value::Int)
    if n == 0
        return 1
    elseif n <= 0
        return 0
    end
    count_ = 0
    for k in max_value:-1:1
        count_ += count_integer_partitions(n-k, min(k, n-k))
    end        
    count_
end

count_integer_partitions(n::Integer) = count_integer_partitions(n, n)

The bounded version requires the slight modification of keeping track of the index so that the correct maximum can be selected. It also includes a zero case.

function count_integer_partitions(n::Integer, max_values::Vector{Int}, idx=1)
    if n == 0
        return 1
    elseif n <= 0
        return 0
    end
    count_ = 0
    max_value = (idx <= length(max_values)) ? min(n, max_values[idx]) : 0
    min_value = (idx + 1 <= length(max_values)) ? 0 : 1
    for k in max_value:-1:min_value
        count_ += count_integer_partitions(n-k, max_values, idx + 1)
    end    
    count_
end
count_integer_partitions(n::Integer) = count_integer_partitions(n, n)

Integer partitions

We can modify the counting formula to instead return arrays. Then we can return the whole set of arrays.

function integer_partitions(n::Integer, max_value::Int)
    if n < 0
        throw(DomainError(n, "n must be nonnegative"))
    elseif n == 0
        return Vector{Int}[[]]
    end
    partitions = Vector{Int}[]
    for k in max_value:-1:1
        for p in integer_partitions(n-k, min(k, n-k))
            push!(partitions, vcat(k, p))
        end
    end        
    partitions
end

In Python you can use the yield keyword to return each partition one at a time. Unfortunately you cannot do that in Julia, but changing to a linear algorithm we can get the same behaviour. See the Linear integer partitions section.

Bounded partitions

For the bounded version we can do a similar modification to its counting function:

function integer_partitions(n::Integer, max_values::Vector{Int}, idx=1)
    if n < 0
        throw(DomainError(n, "n must be nonnegative"))
    elseif n == 0 
        return Vector{Int}[[]]
    end
    partitions = Vector{Int}[]
    max_value = (idx <= length(max_values)) ? min(n, max_values[idx]) : 0
    min_value = (idx + 1 <= length(max_values)) ? 0 : 1
    for k in max_value:-1:min_value
        for p in integer_partitions(n-k, max_values, idx + 1)
            push!(partitions, vcat(k, p))
        end
    end    
    partitions
end

Caching can be added to improve the performance.

Linear

Integer partitions

We can also write these functions in linear stateful versions. With this technique we don’t have to hold the whole array of all partitions in memory. (In Python you could use the yield keyword to accomplish this.)

The state is the last partition and the current index of the value that is being decremented.

First define a struct to be the iterator to dispatch on (see Julia manual: interfaces):

struct IntegerPartitions
    n::Int
    max_value::Int
    function IntegerPartitions(n::Int, max_value::Int)
        if n < 0
            throw(DomainError(n, "n must be nonnegative"))
        end
        new(n, min(max_value, n))
    end
end

IntegerPartitions(n::Int) = IntegerPartitions(n, n)

Base.IteratorSize(::IntegerPartitions) = Base.SizeUnknown()
Base.eltype(::IntegerPartitions) = Vector{Int}

We could use the count_integer_partitions function to get the length. But because this requires some computation, it is better to set the size as Base.SizeUnknown().

Next, we iterate through the partitions as before. But this time instead of jumping to a new function call, we move an index up and down (like a pointer).

function Base.iterate(iter::IntegerPartitions) 
    if iter.n == 0
        return nothing
    end
    parts0 = zeros(Int, iter.n) # shared state that is mutated
    parts0[1] = iter.max_value + 1
    iterate(iter, (parts0, 1))
end

function Base.iterate(iter::IntegerPartitions, state::Tuple{Vector{Int}, Int}) 
    partitions, idx = state
    k = partitions[idx] - 1
    while (k == 0)
        if (idx == 1)
            return nothing
        else
            idx -= 1
            k = partitions[idx] - 1
        end
    end
    partitions[idx] = k
    residue = iter.n - sum(partitions[1:idx])
    i = idx
    while residue != 0
        i += 1
        k = min(k, residue)
        if (k > 1)
            idx += 1
        end
        partitions[i] = k
        residue -= k
    end
    (partitions[1:i], (partitions, idx)) # copy, shared state
end

Example:

for part in IntegerPartitions(5, 3)
    println(part)
end
#[3, 2]
#[3, 1, 1]
#[2, 2, 1]
#[2, 1, 1, 1]
#[1, 1, 1, 1, 1]

Bounded partitions

The struct is similar to before. We will set the maximum of max_values to n here.

struct BoundedPartitions
    n::Int
    max_values::Vector{Int}
    function BoundedPartitions(n::Int, max_values::Vector{Int})
        if n < 0
            throw(DomainError(n, "n must be nonnegative"))
        end
        max_values = copy(max_values)
        for (idx, val) in enumerate(max_values)
            if val > n
                @warn "maximum value=$val > n=$n; setting to n."
                max_values[idx] = n
            end
        end
        new(n, max_values)
    end
end

Base.IteratorSize(::BoundedPartitions) = Base.SizeUnknown()
Base.eltype(::BoundedPartitions) = Vector{Int}

The iterations require a few subtle modifications. Parts which are not modified are not shown.

function Base.iterate(iter::BoundedPartitions) 
    if iter.n == 0
        return nothing
    end
    parts0 = zeros(Int, iter.n) # shared state that is mutated
    parts0[1] = iter.max_values[1] + 1 
    iterate(iter, (parts0, 1))
end

function Base.iterate(iter::BoundedPartitions, state::Tuple{Vector{Int}, Int}) 
    partitions, idx = state
    while (partitions[idx] - 1 < 0) && (idx < length(iter.max_values))
        idx += 1
    end
    k = min(partitions[idx] - 1, iter.max_values[idx])
    while k < 0 || 
        (k + sum(iter.max_values[idx+1:end])) < (iter.n - sum(partitions[1:(idx - 1)]))
        # current value + maximum possible sum < residue
        ...
    end
    ...
    while residue != 0
        i += 1
        k = min(iter.max_values[i], residue)
        if (k > 0)
            idx += 1
        end
        ...
    end
    (partitions[1:i], (partitions, idx)) # copy, shared state
end

Example:

for part in BoundedPartitions(5, [2, 1, 5])
    println(part)
end
#[2, 1, 2]
#[2, 0, 3]
#[1, 1, 3]
#[1, 0, 4]
#[0, 1, 4]
#[0, 0, 5]