realbro

programmer

Integer Partition

What is an integer partition?

I encountered an interesting problem called integer partition while reading Math Girls 1. It’s about counting the ways to express a positive integer as a sum of positive integers, where order doesn’t matter. The book introduces this using an analogy: how many ways can you pay N cents using coins of any denomination (1 cent, 2 cents, 3 cents, and so on)?

For example,

P(1) = 1 :  1 = 1
P(2) = 2 :  2 = 2 = 1 + 1
P(3) = 3 :  3 = 3 = 2 + 1 = 1 + 1 + 1
P(4) = 5 :  4 = 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1

Solution

Although I tried to find a closed-form formula for P(n), I failed. However, I discovered a recurrence relation that allows me to compute it using programming.

To derive this relation, let’s use the coin payment analogy. We can divide the partitions of n into cases based on the largest number used. For instance, some partitions use n as their largest part, others use n-1 as their largest part, and so on down to partitions using only ‘1’s.

To formalize this, I’ll introduce a restricted partition P(n, k), which counts the partitions of n using only integers less than or equal to k. Then the total number of partitions is:

P(n) = P(n, n)     (1)

The key insight is that P(n, k) satisfies the following recurrence relation:

P(n, k) = P(n − k, k) + P(n, k − 1)
with P(0, 0) = 1,  P(n, 0) = 0 for n > 0     (2)

The logic is that partitions of n with maximum part k either use at least one k (in which case, removing one k gives a partition counted by P(n − k, k)) or don’t use k at all (giving P(n, k − 1)).

Actual Code

Based on recurrence relations (2), python code below can calculate P(n):

"""
integer partition is a way of writing n as a sum of positive integers.
For example, 4 can be written as:
    4
    = 3 + 1
    = 2 + 2
    = 2 + 1 + 1
    = 1 + 1 + 1 + 1
where the partition number for 4 is 5.
"""


class Solution:
    """Solution for integer partition."""

    def __init__(self, _n):
        self._n = _n
        size = self._n + 1
        # cache is n+1 * n+1 matrix
        # where cache[i][j] means P(i, j), the partition number for i with max j.
        self._cache = [[None for _ in range(size)] for _ in range(size)]

    def get_partition(self):
        """get partition number for n."""
        return self._sub_partition(self._n, self._n)

    def _sub_partition(self, n, k):
        """P(n k), sub partition for n with max k."""

        # cache hit
        if self._cache[n][k] is not None:
            return self._cache[n][k]

        if k == 0:
            # P(n, 0) = 0 except P(0, 0) = 1
            self._cache[n][k] = 0 if n > 0 else 1
            return self._cache[n][k]

        if n < k:
            # n < k => P(n, k) = P(n, n)
            self._cache[n][k] = self._sub_partition(n, n)
        else:
            # n >= k => P(n, k) = P(n-k, k) + P(n, k-1)
            self._cache[n][k] = self._sub_partition(n - k, k) + self._sub_partition(
                n, k - 1
            )
        return self._cache[n][k]


def main():
    """main function."""
    N = 15
    for target in range(1, N + 1):
        print(f"partition number for {target} is {Solution(target).get_partition()}")


if __name__ == "__main__":
    main()

 

(개인 호스팅 블로그에서 26.02.10에 작성한 글을 옮겼습니다)