2

関数 f(*x) が True を返すすべてのシーケンスを見つけて、n (= 5, fi) 整数の昇順シーケンス x を反復処理する必要があります。

特定の y に対して f_n(*y) が False の場合、z_i >= y_i の任意の z に対して f_n(*z) id False であると仮定します。したがって、 f_n はすべての引数で単調です。

この種のジェネレータ関数を次のように使用して、平方和が 100 未満の整数のすべての昇順シーケンスを決定できます。

for sequence in generate_sequences(5):
   if sum_squares_is_at_least(sequence, 100):
       # some code to trigger the breaking of the generator loop
   else:
       print sequence

明確化: ここでの問題は、n 個の要素を個別に繰り返す必要があることです。最初に、[1,1,1,1,1] を [1,1,1,1,x] に反復し、[1,1,1,2,2] を [1, 1,1,2,y]、最終的には [a,b,c,d,e] で終わります。ジェネレーターは次のように見えるはずですが、必要に応じて for および/または while ループから抜け出すためのコードが必要です (外部で決定されます)。

def generate_sequences(length, minimum = 1):
    if length == []:
        yield []

    else: 
        element = minimum
        while True:

            for sequence in generate_sequences(length - 1, element):
                yield element + [sequence]

            element += 1

例: n = 3 で平方和が 20 以下の場合、次のシーケンスが生成されます: [1, 1, 1]、[1, 1, 2]、[1, 1, 3]、[1, 1, 4]、[1, 2, 2]、[1, 2, 3]、[1, 3, 3]、[2, 2, 2]、[2, 2, 3]

一般的なケースでは、4 が各要素の上限であるという情報を使用できないことに注意してください。これは、大規模な例の実行時間にも深刻な影響を与えます。

4

3 に答える 3

1

itertools.takewhileをお探しですか?

>>> from itertools import takewhile
>>> def gen():  #infinite generator
...    i=0
...    while True:
...       yield range(i,i+5)
...       i = i+1
... 
>>> [ x for x in takewhile( lambda x:sum(x)<20, gen() ) ]
[[0, 1, 2, 3, 4], [1, 2, 3, 4, 5]]
>>>
于 2013-02-20T14:05:03.530 に答える
0

特定のリストから始めて別の数値を追加することにより、再帰で解決します（平方和ターゲットを超えるのを防ぐロジックを使用）

def makegen(N): #make a generator with max sumSquares: N
    def gen(l=[]): #empty list is valid with sum == 0
        yield l
        if l:
            i = l[-1] #keep it sorted to only include combinations not permutations
        else:
            i = 1 #only first iteration
        sumsquare = sum(x*x for x in l) #find out how much more we can add
        while sumsquare + i*i < N: #increase the appended number until we exceed target
            for x in gen(l+[i]): #recurse with appended list
                yield x
            i += 1
    return gen

次の方法でジェネレーター ジェネレーター (tee hee :D) を呼び出すと、必要な最大平方和を取得できます。

for x in makegen(26)():
    print x
于 2016-10-14T19:54:23.920 に答える
0 
import itertools as it

it.takewhile(lambda x: sum_squares_is_at_least(x, 100), generate_sequences(5))

の5について確信が持てる場合は、呼び出されている間はそのままにしておきgenerate_sequencesます。yield

def generate_sequences():
    i = 0 # or anything
    while True:
        yield [i, i] # or anything
        i = i + 1 # or anything

次に、次のように使用します。

it.takewhile(lambda x: sum_squares_is_at_least(x, 100), generate_sequences())
于 2013-02-20T14:02:35.220 に答える