让我们以这样的列表列表为例：
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)
构建树之后，我将提取到达
depth = len(li)的组合我们将不胜感激为构建这样一棵树而提供的任何帮助或任何其他解决问题的想法。谢谢！
最佳答案
因为您的项目及其子项目都已排序，且介于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
关于python - 查找所有乘积大于阈值的列表的笛卡尔乘积的树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57166794/