3
\$\begingroup\$

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?

\$\endgroup\$
3
  • \$\begingroup\$ So just want to confirm. The nested dictionaries represent a tree, where each root-to-leaf path has a path sum equal to the target, namely num? For completeness, the root can be thought of as having a value of zero; all other nodes have non-zero values; node values don't have to be unique. \$\endgroup\$
    – joseville
    Oct 20, 2021 at 15:35
  • \$\begingroup\$ worker(num, lim, dic) populates the input dictionary dic with a tree whose root-to-leaf paths each sum to num s.t. each node in the tree has a value, v, 1 <= v <= lim. \$\endgroup\$
    – joseville
    Oct 20, 2021 at 15:46
  • \$\begingroup\$ Btw, do you actually need to have all the different partitions or just the number of possibles partitions? \$\endgroup\$
    – kubatucka
    Oct 21, 2021 at 9:17

2 Answers 2

3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ @@Xeнεi Ξэnвϵς, one more thing I noticed after writing my answer is that the dictionaries consist of sequential keys, starting from 1. It should make sense as we iterate over i from 1 creating items with i as the keys. All that to say that it should be possible to use lists instead of dicts to represent this tree structure and in fact shouldn't be too hard to make the switch. In general, I would think list access and memory consumption is better than dict's, so making that switch would probably improve things. \$\endgroup\$
    – joseville
    Oct 20, 2021 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.