在Python中通过链接iterables表示递归

Question

我在解决一个二叉树中有水平的问题。我得到了一个级别，然后是一个职位。你知道吗

第二个层次是[True, False]。 第三个层次是[True, False, False, True]。 第四个[True, False, False, True, False, True, True, False]，依此类推。你知道吗

为了解决这个问题，我可能需要多次计算这个序列，以得到该级别上给定位置的元素。你知道吗

对于初始数组pattern = [True, False] 我想做一些类似的事情：

for _ in range(level):
    pattern = pattern + [not elem for elem in pattern]

显然，对于大的限制，这是不适合我。我试图用chain方法从itertools得到一个解决方案，但到目前为止没有结果。用Python来表达这一点，什么是内存有效的方法？你知道吗

编辑

这符合我的要求，但仍然不能满足我所要求的运行时要求。你知道吗

for _ in range(level):
    lsb, msb = tee(pattern)
    pattern = chain(lsb, map(lambda x: not x, msb))

最终，解决方案包括找到所讨论的目标元素的全局索引，并确定从根（基本情况=1）到它的“右”路径有多少条，观察从父级到子级的状态在采用左路径时不会改变，而在采用右路径时会翻转。看来大多数聪明的soln都是对这一事实有一些误解。你知道吗

Answer 1

What is a memory efficient way to express this in Python?

因为您使用的方法将每次迭代所需的内存增加了一倍，所以它不容易扩展。最好找到一种分析方法。你知道吗

下面的生成器需要O（1）个时间来生成每个元素。而且，关键的是，计算下一个值只取决于索引和上一个值。你知道吗

def gen():
    yield True
    n, prev = 1, 1
    while True:
        x = n ^ n - 1
        y = x ^ x >> 1
        if y.bit_length() % 2:
            z = 1 - prev
        else:
            z = prev
        yield bool(z)
        prev = z
        n += 1

这样的递归关系允许计算常量内存中的元素。用cython或pypy实现这个想法应该可以显著提高性能。你知道吗

Answer 2

试图一个接一个地生成元素是个坏主意，而保存所有元素则更糟。您只需要一个元素的值，就可以直接计算它。你知道吗

假设您想要的元素位于索引2**i + k，其中k < 2**i。那么这个元素就是索引k处元素的反，索引k处的元素可以用同样的方法计算。对于所需索引的二进制表示形式中的每一个设置位，您最终会对元素0求反一次。如果有偶数个设置位，则该值为真。否则，该值为False。你知道吗