CODEWITHSUNDEEP
pythonpython-3.xrecursionlist-comprehension
Rushabh Mehta
Rushabh Mehta

Reputation: 1559

Writing list comprehensions dependent on previous values?

I've seen this question before, but it only deals with recursions that are linear in nature. I'm looking for something more general.

Suppose I have the following code

n = 10
num_bits = [0]
for i in range(n):
    nums_bits.append(num_bits[i>>1]+i%2)

This code will compute num_bits, a 11 element array of value with num_bits[i] representing the number of bits it takes to represent i.

Is it possible to write this as a list comprehension? Something like this doesn't work

num_bits = [0]*11
num_bits = [num_bits[i>>1]+i%2 for i in range(11)]

since the comprehension doesn't update the value of num_bits in the middle of evaluation. Is there a canonical way to do something like this, besides a for loop?

P.S. I'm aware there are other ways to solve this problem: I'm just using it as a vehicle to understand Python's features better.

Edit: To summarize, I'd like to know what the proper way of generating lists of values that are dependent on previous values is. For a simpler example, consider the Fibonacci Numbers

fibonacci = [0,1]
for i in range(10):
    fibonacci.append(fibonacci[-1]+fibonacci[-2])

Is there a way to generate these numbers in a comprehension? If not, what tools are there for this other than for loops (or are for/while loops my only option)?

Upvotes: 1

Views: 517

Answers (2)

Pynchia
Pynchia

Reputation: 11590

Given it is not a piece of code I'd recommend, for the reasons discussed in the comments above and in the other answer, this comprehension should be faster than the for loop:

fibonacci = [0,1]
deque((fibonacci.append(fibonacci[-1]+fibonacci[-2]) for _ in range(10)), maxlen=0)

as it fills the list consuming the generator and discarding the result (an empty queue, it's the fastest recommended way to consume an iterator)

It produces:

>>> fibonacci
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

Upvotes: 1

LeopardShark
LeopardShark

Reputation: 4416

No.

There is no nice way to do this with a list comprehension, and that is not what they’re for. The purpose of list comprehensions is to offer a more readable alternative to maps and filters, and this isn’t that, so it’s not possible to do this in a sensible way.

Upvotes: 1

Related Questions