python - 使用列表列表查找所有加起来等于给定数字 python 的组合

Question

我看过很多关于如何用一个列表找到所有加起来等于一个数字的组合的帖子，但我想知道如何扩展它，这样你一次只能从一个列表中选择一个数字列表

问题:
您必须从每个列表中选择 1 个数字，如何找到总和为 N 的所有组合？

给定:
3 个不同固定长度的列表 [例如l1 总是有 6 个值，l2 总是有 10 个值，等等]:

l1 = [0.013,0.014,0.015,0.016,0.017,0.018]
l2 = [0.0396,0.0408,0.042,0.0432,0.0444,0.045,0.0468,0.048,0.0492,0.0504]
l3 = [0.0396,0.0408]

期望的输出:
如果 N = .0954，则输出为 [0.015, 0.396, 0.408],[0.015, 0.408, 0.0396]。

我尝试过的:

output = sum(list(product(l1,l2,l3,l4,l5,l6,l7,l8)))

然而，这过于密集，因为我最大的桶有 34 个值，创建了太多组合。

任何有关如何以更有效的方式处理此问题的帮助/提示，​​我们将不胜感激!

Answer 1

非递归解决方案:

from itertools import accumulate, product
from sys import float_info

def test(lists, target):
    # will return a list of 2-tuples, containing sum and elements making it
    convolutions = [(0,())]
    # lower_bounds[i] - what is the least gain we'll get from remaining lists
    lower_bounds = list(accumulate(map(min, lists[::-1])))[::-1][1:] + [0]
    # upper_bounds[i] - what is the max gain we'll get from remaining lists
    upper_bounds = list(accumulate(map(max, lists[::-1])))[::-1][1:] + [0]
    for l, lower_bound, upper_bound in zip(lists, lower_bounds, upper_bounds):
        convolutions = [
            # update sum and extend the list for viable candidates
            (accumulated + new_element, elements + (new_element,))
            for (accumulated, elements), new_element in product(convolutions, l)
            if lower_bound - float_info.epsilon <= target - accumulated - new_element <= upper_bound +  float_info.epsilon
        ]

    return convolutions

test(lists, target) 的输出:

[(0.09540000000000001, (0.015, 0.0396, 0.0408)),
 (0.09540000000000001, (0.015, 0.0408, 0.0396))]

这可以通过使用 bisect 对列表进行排序并根据上限/下限对其进行切片来进一步优化:

from bisect import bisect_left, bisect_right
# ...

convolutions = [
    (partial_sum + new_element, partial_elements + (new_element,))
    for partial_sum, partial_elements in convolutions
    for new_element in l[bisect_left(l, target-upper_bound-partial_sum-float_info.epsilon):bisect_right(l, target-lower_bound-partial_sum+float_info.epsilon)]
]