representing recurrence by chaining iterables in Python

Question

I'm solving a problem where I have levels in a binary tree. I'm given a level, then a position.

The second level is [True, False]. The third level is [True, False, False, True]. The fourth [True, False, False, True, False, True, True, False], and so on.

To solve the problem, I may need to calculate this sequence out many times to get the element at a given position at that level.

For the initial array pattern = [True, False] I want to do something like:

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

Obviously for large limits this is not working well for me. My attempts at a solution using the chain method from itertools has so far been fruitless. What is a memory efficient way to express this in Python?

EDIT

This did what I was looking for, but still did not meet the runtime requirements I was looking for.

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

Ultimately, the sol'n involved finding the global index of the target element in question, and determining how many 'right' paths were taken from the root (base case = 1) to get to it, observing that the state from the parent to child does not change if a left path was taken, but flips if a right path was taken. It appears that most of the clever soln's are some spin on this fact.

Answer 1

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

Since the approach you're using doubles the memory needed on each iteration, it won't scale easily. It may be better to find an analytic approach.

The generator below takes O(1) time to generate each element. And, crucially, calculating the next value depends only on the index and the previous value.

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

A recurrence relation like this allows to compute elements in constant memory. Implementing the idea with cython or pypy should increase performance significantly.