-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 に答える