生成给定某个产品的列表的所有子集而不迭代整个powerset？ （蟒蛇）

Question

可能重复：
Finding all possible combinations of numbers to reach a given sum生成给定某个产品的列表的所有子集而不迭代整个powerset？ （蟒蛇）

我不想因为它输出的顺序，我不想要的东西用Itertools不能使用（我需要能够评估组合发生器试图输出什么，以决定是否要继续沿着该分支行进）。

例如，假设我有一个列表[1,2,3,4,5]，并且我想输出具有完整产品< = 12的组合，而不会浪费迭代。如果我生成[1,2,3]，这很好，因为1 * 2 * 3 = 6。但是如果我尝试[1,2,3,4]，然后1 * 2 * 3 * 4 = 24，并且这大于12，所以我甚至不会打扰到[1,2,3,5]或[1,2,4,5]等等。

当前的尝试：

from operator import mul 

mylist=[1,2,3,4,5] 
limit=12 

def productOK(mylist): #but this can be any conditional, theoretically 
    if reduce(mul, mylist) > limit: 
     return False 
    return True 


def generateValidSubsets(mylist): 
    for r in range(1,len(mylist)+1): 
     start=mylist[:r] 
     if productOK(start)==False: break 
     #not sure how to recombine in the right order otherwise 
     yield start 



for combo in generateValidSubsets(mylist): 
    print combo 

我要去哪里错了？

Answer 1

我强烈建议您切换到递归实现。这将让您更轻松地实施裁员：

def subs(target, universe, currentsubs, currentproduct, goodsubs): 
    first_from_universe_not_in_currentsubs = # an exercise for the reader 
    newsubs = [first_from_universe_not_in_currentsubs] + currentsubs 
    newproduct = currentproduct * first_from_universe_not_in_currentsubs 
    if newproduct == target: 
     return goodsubs + [newsubs] 
    elif newproduct > target: 
     return goodsubs 
    else: 
     return subs(target, universe, newsubs, newproduct, goodsubs) 

subs(12, [1,2,3,4,5], [], 0, []) 

即使你填空上面，它可能不是很正确，但它确实表明，你怎么能实现晋级。