通过在 Python 中链接可迭代对象来表示循环

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]

显然，对于较大的限制，这对我来说效果不佳。到目前为止，我尝试使用 itertools 中的 chain 方法来解决问题，但没有结果。在 Python 中表达这一点的内存有效方式是什么？

编辑

这满足了我的要求，但仍然不符合我正在寻找的运行时要求。

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

最终，解决方案涉及找到相关目标元素的全局索引，并确定有多少 'right' 从根（基本情况 = 1）到它的路径，观察如果采用左路径，从父级到子级的状态不会改变，但如果采用右路，则状态会翻转。看来大多数聪明的解决方案都是基于这个事实。

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。如果有偶数个设置位，则值为 True。否则，值为 False。

通过在 Python 中链接可迭代对象来表示循环

representing recurrence by chaining iterables in Python

python

iterable

python-3.x