-2

可能重复：
找到所有可能的数字组合以达到给定的总和

我不想使用 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

我哪里错了？

4

1 回答 1

0

我强烈建议您切换到递归实现。这将允许您更轻松地实施削减：

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, [])

即使您填写了上面的空白，它也可能不太正确，但它确实向您展示了如何实现切割。

于 2012-04-18T14:27:19.300 回答