Python program to find all possible ways an integer num can be expressed as sum of integers between 1 and lim

Question

This is a Python program that finds all possible ways a positive integer num can be expressed a sum of a number of integers between 1 and lim (including both ends).

There is no limit on the number of integers, duplicates are allowed, same elements in different order is considered different.

The output is a nested dictionary. Each key is a possible integer, each key in the nested dictionary is a possible integer in the series formed by the keys of the parent dictionaries in the previous levels that allows or makes the series sum to num.

From any last level keys, through the keys in the parent dictionaries, to the first level parent key, the sum of such a series is always num.

The Code

def partition_tree(num: int, lim: int) -> dict:
    """take a positive integer `num` and a positive integer `lim`,
    calculate all possible ways integer `num` can be expressed as,
    a summation of integers between 1 and `lim`, returns a tree"""
    d = dict()
    if any(not isinstance(i, int) for i in (num, lim)):
        raise TypeError('The parameters of this function should be `int`s')
    if any(i <= 0 for i in (num, lim)):
        raise ValueError('The parameters should be both greater than 0')
    def worker(num: int, lim: int, dic: dict) -> None:
        for i in range(1, lim+1):
            n = num - i
            if n:
                dic.setdefault(i, dict())
                worker(n, lim, dic[i])
            else:
                dic.update({i: 0})
                break
    worker(num, lim, d)
    return d

Example output:

def partition_tree(num: int, lim: int) -> dict:
    """take a positive integer `num` and a positive integer `lim`,
    calculate all possible ways integer `num` can be expressed as,
    a summation of integers between 1 and `lim`, returns a tree"""
    d = dict()
    if any(not isinstance(i, int) for i in (num, lim)):
        raise TypeError('The parameters of this function should be `int`s')
    if any(i <= 0 for i in (num, lim)):
        raise ValueError('The parameters should be both greater than 0')
    def worker(num: int, lim: int, dic: dict) -> None:
        for i in range(1, lim+1):
            n = num - i
            if n:
                dic.setdefault(i, dict())
                worker(n, lim, dic[i])
            else:
                dic.update({i: 0})
                break
    worker(num, lim, d)
    return d

import json
print(json.dumps(partition_tree(6, 3), indent=4))

Output:

{
    "1": {
        "1": {
            "1": {
                "1": {
                    "1": {
                        "1": 0
                    },
                    "2": 0
                },
                "2": {
                    "1": 0
                },
                "3": 0
            },
            "2": {
                "1": {
                    "1": 0
                },
                "2": 0
            },
            "3": {
                "1": 0
            }
        },
        "2": {
            "1": {
                "1": {
                    "1": 0
                },
                "2": 0
            },
            "2": {
                "1": 0
            },
            "3": 0
        },
        "3": {
            "1": {
                "1": 0
            },
            "2": 0
        }
    },
    "2": {
        "1": {
            "1": {
                "1": {
                    "1": 0
                },
                "2": 0
            },
            "2": {
                "1": 0
            },
            "3": 0
        },
        "2": {
            "1": {
                "1": 0
            },
            "2": 0
        },
        "3": {
            "1": 0
        }
    },
    "3": {
        "1": {
            "1": {
                "1": 0
            },
            "2": 0
        },
        "2": {
            "1": 0
        },
        "3": 0
    }
}

I came up with this in under 2 minutes and made it work in one try. I made this for use in my project to generate pseudowords, more specifically to calculate all possible ways a given word length num can be achieved using chunks of lengths 1 to lim.

How is the performance, coding style and memory consumption of my code (try partition_tree(18, 6), something like this can be in common use)? How can it be improved?

Answer 1

Recursion Improvements

In your problem, you end up calling the same recursive function multiple times. For example for partition_tree(6, 3) calls worker(2, 3, d) many many times albeit with updated dictionaries. This ends up costing you quite a bit of performance. You could avoid recomputing the same combinations by using memoization. Meaning you would save the outputs of your previous calls.

Python's functools makes it incredibly easy to implement memoization with the @lru_cache decorator:

@lru_cache(maxsize=None)
def worker(*args):
   ...

If we're to save calls to the function, we can't be passing around dictionaries or prefixes. It has to be a pure function. And limit doesn't change within the partition tree and therefore it doesn't need to be passed around either. So let's remove those arguments and do the updating ourselves:

from functools import lru_cache

def partition_tree_lru(num: int, lim: int) -> dict:
    """take a positive integer `num` and a positive integer `lim`,
    calculate all possible ways integer `num` can be expressed as,
    a summation of integers between 1 and `lim`, returns a tree"""

    if any(not isinstance(i, int) for i in (num, lim)):
        raise TypeError('The parameters of this function should be `int`s')
    if any(i <= 0 for i in (num, lim)):
        raise ValueError('The parameters should be both greater than 0')

    @lru_cache(maxsize=None)
    def worker(num: int) -> dict:
        working_dict = {}
        for i in range(1, lim+1):
            n = num - i
            if n:
                working_dict[i]=worker(n)
            else:
                working_dict[i]=0
                break
        return working_dict
    
    return worker(num)

Improvement:

function [partition_tree_lru]((50, 50)) finished in 1 ms
function [partition_tree]((20, 10)) finished in 570 ms

Note : if 'you're going to be calling the partition_tree multiple times for different inputs it would be worth moving the worker function definition to the outer scope so that the cache persists between calls.

Answer 2

In terms of code structure, here are my suggestions:

1. Move d = dict() to after the argument checks, so that you only create the dictionary if the inputs are valid.

2. The if/else statements inside the for loop can be removed:

           for i in range(1, lim+1):
               n = num - i
               if n:
                   dic.setdefault(i, dict())
                   worker(n, lim, dic[i])
               else:
                   dic.update({i: 0})
                   break
   

   becomes:

           for i in range(1, min(num, lim+1)):
               n = num - i
               dic.setdefault(i, dict())
               worker(n, lim, dic[i])
           if num <= lim:
               dic.update({num: 0})
   

3. Additionally, dic.setdefault(i, dict()) has two modes. One for when the input key doesn't exist and one for when it does exists. I believe that within your code you're only ever hitting the latter mode (key doesn't exist), so dic.setdefault(i, dict()) can be replaced with dic[i] = dict().

4. Lastly, dic.update({num: 0}) can be replaced with dic[num] = 0 which would prevent you from creating the {num: 0} dictionary input to dic.update.

---

With all those changes, the code becomes:

def partition_tree(num: int, lim: int) -> dict:
    """take a positive integer `num` and a positive integer `lim`,
    calculate all possible ways integer `num` can be expressed as,
    a summation of integers between 1 and `lim`, returns a tree"""
    if any(not isinstance(i, int) for i in (num, lim)):
        raise TypeError('The parameters of this function should be `int`s')
    if any(i <= 0 for i in (num, lim)):
        raise ValueError('The parameters should be both greater than 0')
    d = dict()
    def worker(num: int, lim: int, dic: dict) -> None:
        for i in range(1, min(num, lim+1)):
            n = num - i
            dic[i] = dict()
            worker(n, lim, dic[i])
        if num <= lim:
            dic[num] = 0
    worker(num, lim, d)
    return d

I ran this code on your input:

import json
print(json.dumps(partition_tree(6, 3), indent=4))

and it produced the same output as your code.

---

In terms of code readability, I would suggest renaming d and dic to tree or something that indicates that the dictionaries represent a tree. I would also suggest renaming num to target or target_sum or just sum_ -- if take this suggestion, also consider renaming lim to max_num or max_; i to num; and n to new_target or new_target_sum or new_sum_ as appropriate. Also consider renaming worker to dfs since that's basically what it is doing and dfs is more descriptive than worker.

With some of the readability changes, the code looks like this:

def partition_tree(target_sum: int, max_num: int) -> dict:
    """take a positive integer `num` and a positive integer `lim`,
    calculate all possible ways integer `num` can be expressed as,
    a summation of integers between 1 and `lim`, returns a tree"""
    if any(not isinstance(i, int) for i in (target_sum, max_num)):
        raise TypeError('The parameters of this function should be `int`s')
    if any(i <= 0 for i in (target_sum, max_num)):
        raise ValueError('The parameters should be both greater than 0')
    tree = dict()
    def worker(target_sum: int, max_num: int, tree: dict) -> None:
        for num in range(1, min(target_sum, max_num+1)):
            new_target_sum = target_sum - num
            tree[num] = dict()
            worker(new_target_sum, max_num, tree[num])
        if target_sum <= max_num:
            tree[target_sum] = 0
    worker(target_sum, max_num, tree)
    return tree

This code still produces the same output as your original code.

Answer 3

I can't see why there is an upper limit. The size of the list can never exceed the function input number. So there is always a limit. And also as the summation numbers become larger, the list size becomes smaller. So there are no problems with removing the limit parameter. The code will not run forever when given a limit.

Perhaps you have some special case for limiting the summation numbers. I don't know, but it seems like this function has limited usefulness as a general function, and is checking to many things for no reason.

I can imagine that if I was using this function I would always provide a limit that is equal to the target sum. Because I would want a function to return all possibilities.

I guess there could be specific cases where a limit is required, but I would trim to that outside of the function. Perhaps the limiter might be useful for numbers in the billions. Still I wonder about time of completing the task or whether the code samples about will reach recursion limits. I know they will in the billions.

So my question is: why limit your function?

I say this, because I came here looking to find all sets of summations to an integer. But I had no need for limiting these summation numbers. And I couldn't think of a case where I would want to do that. The question must be a special case and not a general multi-purpose function. I think the special properties should be removed from code samples to make this generally useful to people looking for such code.