时间戳

首页 > 解决方案 > 在字典中查找产生一定总和的键组合

python - 在字典中查找产生一定总和的键组合

问题描述

我有一个dict这样的：

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

我试图得到所有产生的组合，keys可以重复。value sumxkeys

因此，例如，目标3.12可能是["a", "a", "a"]

我写了这样的代码：

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))

但这一直在旋转而没有结果，我在阅读了这个答案后编辑了我的代码。所以我不确定它是否有效，或者它只是陷入了无限循环，如果没有，这是否是解决这个问题的最佳方法。

标签： pythondictionarycombinations

解决方案

如前所述，不要相信float完全平等。但是，您可以使用math.isclose：

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()))

推荐阅读