Distinct partitions of an integer excluding repetitious combinations

Question

I found this code online somewhere and I'm trying to make sense of how it works. You supply the partitions() function with an integer and the code returns the number of distinct partitions that do NOT include repeating numbers (e.g. n = 5 -> 2 partitions (3,2) & (4,1)). I'd like to understand how exactly this recursive solution is managing this. I've been toying with the code, tracking the recursion calls, and I still can't quite understand how it works. Please help me understand.

def partitions(n):
    memo = [[0 for _ in range(n + 2)] for _ in range(n + 2)]
    return bricks(1, n, memo) - 1

def bricks(h, l, memo):
    if memo[h][l] != 0:
        return memo[h][l]
    if l == 0:
        return 1
    if l < h:
        return 0

    memo[h][l] = (bricks(h + 1, l - h, memo)) + (bricks(h + 1, l, memo))
 
    return memo[h][l]

score 1 · Answer 1 · answered Jun 25 '20 at 05:22

This appears to be OEIS A111133, the number of partitions of n into at least 2 distinct parts.

Forget all the cruft with memo - that's just an optimization, and obscures the intent. The variable names in what remains are terrible. I'll use L and H instead (at least L isn't - like l - easily confusable with the digit 1).

bricks(H, L) appears to be the number of partitions of L into distinct parts the least of which is at least H. How many of those are there? Well, H is in such a partition, or it's not. If H is, then L-H remains, and that needs to be partitioned into parts the least of which is at least H+1. If H is not in such a partition, then L remains, and needs to be partitioned into parts the least of which is at least H+1. Adding those mutually exclusive cases together:

bricks(H, L) = bricks(H+1, L-H) + bricks(H+1, L)

If L < H, there are no partitions of L with a part at least H, so 0. Since bricks(L, L) must be 1 (there's obviously 1 partition of L with least part at least L), that requires bricks(H, 0) to return 1 for the sum above to work out.

Finally, the number of partitions of n into at least 2 distinct parts is the number of partitions of n into distinct parts the least of which is at least 1 - bricks(1, n) - less the singleton partition {n} (that partition doesn't have at least 2 distinct parts).

It's not the code itself that's a barrier to understanding here - it's figuring out the thoughts behind the code.

It might be worth noting that the `l == 0` base case could be more straight-forwardly tested with `l == h`. It recurses a little bit less, but gets the same result. — Blckknght, Jun 25 '20 at 05:26
Right. I'm not aiming to improve the code, but to reconstruct the thinking behind the code exactly as given. The `L == 0` case is senseless on its own, and, best I can tell, can only be justified via the reasoning I spelled out in the answer: "otherwise it wouldn't work" ;-) Checking for `L == H` instead would make sense on its own. — Tim Peters, Jun 25 '20 at 17:31

EntangledLoops · Answer 2 · 2020-06-25T04:28:15.303

At a glance, it looks like memoization along the lines of "equal partition subset sum".

You probably got the code from an answer here: https://leetcode.com/problems/partition-equal-subset-sum/

And you can find a description of how it works there or here: https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews/3jEPRo5PDvx

The general idea here is to start with n and ask "how can I compute n from the subset of numbers split in each possible way"? (The split occurs at the recursive call memo[h][l] = (bricks...). Each recursion may further split to try and form whatever difference is remaining from the previous split, etc.

Note: It seems like "h" and "l" are backwards here if they are meant to be "high" and "low", respectively.

Distinct partitions of an integer excluding repetitious combinations

2 Answers2