python - 用于查找乘积大于阈值的列表的所有笛卡尔乘积的树

Question

让我们举一个这样的列表示例:

li=[[0.99, 0.002],
 [0.98, 0.0008, 0.0007],
 [0.97, 0.009, 0.001],
 [0.86, 0.001]]

请注意，每个子列表中的元素按降序排序，并且它们的总和始终小于或等于 1。此外，子列表本身按其第一个元素的降序排序。

我有兴趣找到组合，从每个子列表中取出一个元素，使得组合元素的乘积高于某个阈值，例如 1e-5。我发现执行此操作的一种方法是使用 itertools.product。

a = list(itertools.product(*li))
[item for item in a if np.prod(item)>1e-5]

但是，这个过程对我来说不可行，因为我的实际列表有太多子列表，因此要检查的可能组合数量太大。

我必须做相反的事情，即只找到满足给定条件的组合，而不是首先找到所有组合并检查阈值条件。例如:由于 0.002*0.0008*0.009 已经小于 1e-5，所以我可以忽略以 (0.002, 0.0008,0.009,...) 开头的所有其他组合。

我找不到一个简单的方法来实现这个。我想到的是树数据结构，我在其中构建一棵树，以便每个节点都将跟踪产品，并且一旦节点值低于 1e-5，我就停止在该节点上进一步构建树，并且在右侧的节点上(因为右侧的节点将小于当​​前节点)。

一个简单的树骨架开始:

class Tree(object):
    def __init__(self, node=None):
        self.node = node
        self.children = []

    def add_child(self, child):
        self.children.append(child)

一旦树构建完成，我就会提取达到深度 = len(li) 的组合

任何帮助构建这样一棵树或任何其他解决问题的想法将受到高度赞赏。谢谢!

Answer 1

由于您的项目及其子项目均已排序且介于 0 和 1 之间，因此 itertools.product 的输出不会增加。数学。正如您指出的那样，这并不奇怪，但是您如何利用这一点......

我认为您想要的是 itertools.product 的副本，并提供在产品低于阈值时立即修剪分支的快捷方式。这将使您能够高效地迭代所有可能的匹配项，而无需浪费时间重新检查您已经知道无法满足阈值的产品。

我在这里找到了 itertools.product 的迭代器实现:how code a function similar to itertools.product in python 2.5 (我正在使用 python 3，它似乎工作正常。)

所以我只是复制它，并在循环内插入阈值检查

# cutoff function
from functools import reduce
from operator import mul

threshold = 1e-5

def cutoff(args):
    if args:
        return reduce(mul, args) < threshold
    return False

# alternative implementation of itertools.product with cutoff
def product(*args, **kwds):
    def cycle(values, uplevel):
        for prefix in uplevel:       # cycle through all upper levels
            if cutoff(prefix):
                break
            for current in values:   # restart iteration of current level
                result = prefix + (current,)
                if cutoff(result):
                    break
                yield result

    stack = iter(((),))             
    for level in tuple(map(tuple, args)) * kwds.get('repeat', 1):
        stack = cycle(level, stack)  # build stack of iterators
    return stack

# your code here
li=[[0.99, 0.002],
    [0.98, 0.0008, 0.0007],
    [0.97, 0.009, 0.001],
    [0.86, 0.001]]

for a in product(*li):
    p = reduce(mul, a)
    print (p, a)

如果我忽略截止值，然后稍后检查 p > 阈值，我会得到相同的结果。

(0.99, 0.98, 0.97, 0.86) 0.8093408399999998
(0.99, 0.98, 0.97, 0.001) 0.0009410939999999998
(0.99, 0.98, 0.009, 0.86) 0.007509348
(0.99, 0.98, 0.001, 0.86) 0.0008343719999999999
(0.99, 0.0008, 0.97, 0.86) 0.0006606864
(0.99, 0.0007, 0.97, 0.86) 0.0005781006
(0.002, 0.98, 0.97, 0.86) 0.0016350319999999998
(0.002, 0.98, 0.009, 0.86) 1.5170399999999998e-05