Python如何生成所有对项

Question

我想要一个所有“成对术语”的无限生成器。其中 0 是对项，两个对项的元组 (a,b) 是对项。重要的是每个项目至少出现一次(在有限的时间内)，但只出现一次会更有效率。

我想到了

def pairTerms():
  yield 0
  generated=[]
  diagonal=-1 #sum indices in generated of the pairs we are generating, could be replaced by len(generated)-1
  for t in pairTerms():
    generated.append(t)
    diagonal+=1
    for i,a in enumerate(generated):
      yield (a,generated[diagonal-i])

但这很快就会填满内存。 编辑:这种方法实际上似乎工作得很好，在填满内存之前生成了超过 1000 万个术语。

或者:

def pairTermsDepth(depth):   
  yield 0 
  if depth:
      for a in pairTermsDepth(depth-1):
        for b in pairTermsDepth(depth-1):
          yield (a,b)

def pairTerms():
  i=0
  while True:
    for item in pairTermsDepth(i):
      i+=1
      yield item

但这有一个缺点，即当达到新的 while 迭代并耗尽堆栈时，会重新列出所有旧术语。

注意:我不太清楚如何标记这个问题，请随意更改它们。

Answer 1

下面的方法可以在我的电脑半分钟内找到前1亿个词条(打印出来会花更长的时间)，生成前N个词条的内存占用是O (平方(N))。

def pair_terms() :
    yield 0

    # By delaying this recursion until after a yield, we avoid
    # an infinite recursive loop.
    generated = []
    generator = pair_terms()
    this = generator.next()

    while True:
        for j in range(len(generated)):
            yield (this, generated[j])
            yield (generated[j], this)
        yield (this, this)
        generated.append(this)
        this = generator.next()

诀窍在于，要生成第 n 个项，我只需要保留不超过 sqrt(n) 的项记录。我通过让生成器递归调用自身来做到这一点。这似乎是额外的工作，但由于您只进行了 O(sqrt(n)) 递归调用，因此与生成结果相比，递归调用的开销是一个舍入误差。