A weird algorithm for sharing coins

Here's a memorable problem from Project Euler:

There are 7 ways to separate 5 coins into piles (as shown). How about 100 coins?

OOOOO
OOOO   O
OOO   OO
OOO   O   O
OO   OO   O
OO   O   O   O
O   O   O   O   O

Solution

In number theory, it is known as the partition function: $p(k)$. So $p(5) = 7$. A simple formula for $p(n)$ is currently unknown but, we can calculate it recursively. The key insight is how we break $p(n)$ into smaller problems.

Let $p(n, k)$ be the number of ways to arrange of $n$ coins into piles allowing up to $k$ coins per pile. For example, $p(4, 2)$ is:

OO   OO
OO   O   O
O    O   O   O

Let's build the recurrence.

• If $k = 1$, we can only put 1 coin in each of the $n$ piles; if $n=1$, there's only one coin. There's only one arrangement in either case. Therefore,

$$p(n, 1) = p(1, k) = 1$$

• The possible arrangements for $n, k$ can be segregated into two categories:
  1. Those that only use smaller piles of $k-1$ coins or less.
  2. And the rest — with a pile of $k$ coins. If we remove it, we are left with all possible ways to arrange $n-k$ coins.

$$p(n, k) = p(n, k-1) + p(n-k, k)$$

A concrete example

To be certain that we understand, let's divide $p(5, 3)$ into these two groups. The first group $p(n, k - 1)$ has all arrangements with piles of size $k - 1 = 2$ or less.

OO   OO   O
OO   O   O   O
O   O   O   O   O

The 2nd group contains one pile of size 3. If we remove it, we are left with $p(2, 2)$.

000   OO
000   O   O

Adding these two counts, we can see that $p(5, 3) = 5$. Let's calculate $p(5, 3)$ recursively now.

What if $n \leq 0$?

We missed a base case; $p(0, 2)$ came from $p(2, 2)$ after making a common pile of 2 coins; we need one arrangement to put the common pile. Though it seems a bit counterintuitive, we need to set:

$$p(0, k) = 1$$

During recursion, we will encounter calls like $p(2, 3)$. Blindly expanding will result in negative values for $n$:

$$p(2, 3) = p(2, 2) + p(-1, 3)$$

We can add a maximum of $n$ coins to a pile. So we can set $k$ to $n$ when $k > n$.

$$p(2, 4) = p(2, 2)$$

Writing the code

Let's write an implementation of our 4 base cases and the recurrence and use it to compute $p(100, 100)$.

fn partitions(n: usize) -> usize {
    fn partitions_helper(n: usize, k: usize) -> usize {
        if k > n {
            partitions_helper(n, n)
        } else if n == 0 || n == 1 || k == 1 {
            1
        } else {
            partitions_helper(n, k - 1) + partitions_helper(n - k, k)
        }
    }
    partitions_helper(n, n)
}

fn main() {
    println!("{}", partitions(100));
}

After about a second, we are greeted with the answer.

190569292

Speeding it up

A lot of values are computed again and again. For instance,

If we continue expanding the first 2 terms, we will encounter $p(2, 2)$ twice. It makes sense to use caching a.k.a memoization with crates like cached. With caching, this problem goes from exponential to quadratic time complexity i.e $O(e^{n})$ to $O(n^2)$ — a gap so huge that calculating $p(1000)$ would shrink from days to under a second.

use cached::proc_macro::cached;
...
    // Just add this proc macro to above code. That's it!
    #[cached]
    fn partitions_helper(n: isize, k: isize) -> isize {
    ...

Bottom-up approach

Instead of caching previously computed recursive calls, we can avoid the stack overhead by just starting from the base and building up higher and higher until we reach the answer. This approach is cleaner and faster.

fn partitions_bottom_up(n: usize) -> usize {
    let mut partitions = vec![vec![0; n + 1]; n + 1];

     fill all the base cases
    for i in 0..=n {
        partitions[0][i] = 1;
        partitions[1][i] = 1;
        partitions[i][1] = 1;
    }

     build up the rest of the n, k values
    for i in 2..=n {
        for j in 2..=n {
            partitions[i][j] = partitions[i][j - 1];
            if i >= j {
                partitions[i][j] += partitions[i - j][j];
            }
        }
    }

    partitions[n][n]
}