Finding combinations of keys in a dict that produce a certain sum

Question

I have a dict like so:

a = {"a" : 1.04,
     "b" : 1.07,
     "c" : 10.99,
     ...}

I am trying to get all of the combinations of keys that value sum produces x, there can be repeating keys.

So for example a target of 3.12 can be a result of ["a", "a", "a"]

And I wrote a code like so:

def combinations(data, target, result = [], partial_target = 0):
    if partial_target == target:
        yield result
    if partial_target >= target:
        return
    for key, value in data.items():
        yield from combinations(data, target, result + [key], partial_target + value)


list(combinations(a, 199.45))

But this keeps on spinning forever with no result, I edited my code after reading this answer. So I am not sure if it works or its just stuck in an infinite loop, and if not, if this is the optimal way to solve this problem.

Don't trust floats to work like that; I'd suggest testing whether the partial_target is _close to_ target. — jonrsharpe, Jul 16 '21 at 11:41
PSA: Be warned of [floating point math](https://stackoverflow.com/questions/588004/is-floating-point-math-broken). It does not always behave as you'd expect. — DeepSpace, Jul 16 '21 at 11:41
But if I would pass `result = None / if result == None : result = []`, each loop the `result` would be reset to be an empty list? — Jonas Palačionis, Jul 16 '21 at 11:44

user2390182 · Answer 1 · 2021-07-16T12:15:29.233

As has been mentioned, do not trust float for exact equality. You can use math.isclose, however:

import math

def combinations(data, target):
    def inner(target, pool):
        if math.isclose(0.0, target, abs_tol=0.00001):
            yield []
            return
        if target < 0:
            return
        for i, key in enumerate(pool):
            for c in inner(target - data[key], pool[i:]):
                yield c + [key]

    return inner(target, tuple(data.keys()))

chatax · Accepted Answer · 2021-07-16T12:09:48.527

1

To speed up your calculations you could define a max_keys that defines the maximum length of your key combinations.

from itertools import combinations_with_replacement
from math import isclose

test_dict = {
    "a" : 1.04,
     "b" : 1.07,
     "c" : 10.99,
     "d" : 1.56}

def get_target_combinations(dictionary, target, max_keys=3):
    filtered = {key: value for key, value in dictionary.items() if value < target}
    for num_combs in range(2, max_keys+1):
        combs = combinations_with_replacement(filtered.keys(), r=num_combs)
        for keys in combs:
            if isclose(sum(map(lambda x: dictionary[x], keys)), target):
                yield keys
        
        
list(get_target_combinations(test_dict, 3.12, max_keys=4))
>> [('d', 'd'), ('a', 'a', 'a')]

edited Jul 16 '21 at 12:09

answered Jul 16 '21 at 11:56

chatax

990
3
17

It looks like even with `max_keys = 5` and `len(dict) = 1000` it takes time. Thank you for your solution. – Jonas Palačionis Jul 16 '21 at 11:59
This quite terrible algorithmically. Vastly overproducing combinations... – user2390182 Jul 16 '21 at 12:13
This code takes 2min 13s on `len(dict) = 1000` and `max_keys = 5` – chatax Jul 16 '21 at 12:16

Finding combinations of keys in a dict that produce a certain sum

2 Answers2