带有外部结束条件的Python生成器

Question

我需要遍历一些升序的整数序列 x，假设 n = 5，找出所有让一个函数 f(*x) 返回 True 的序列。

假设如果对于某个特定的 y，f_n(*y) 返回 False，那么对于任何 z，只要 z_i 大于等于 y_i，f_n(*z) 也会返回 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 是每个元素的上限这一信息。这也会严重影响在更大例子中的运行时间。

Answer 1

我会用递归的方法来解决这个问题。首先从一个给定的列表开始，然后再加上一个数字（要加上逻辑，防止超过平方和的目标）。

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

以这种方式调用我们的生成器（哈哈 :D），可以让我们得到任何我们想要的最大平方和。

for x in makegen(26)():
    print x

Answer 2

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())

Answer 3

你是在找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]]
>>>