生成給定某個產品的列表的所有子集而不迭代整個powerset？ （蟒蛇）

Question

可能重複：
Finding all possible combinations of numbers to reach a given sum

我不想因爲它輸出的順序，我不想要的東西用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, []) 

即使你填空上面，它可能不是很正確，但它確實表明，你怎麼能實現晉級。