[Tutor] Son of Bonacci

avi.e.gross at gmail.com avi.e.gross at gmail.com
Tue Aug 16 12:47:36 EDT 2022


Although the one asking the question is AWOL, I want to share a sort on
one-liner from a book I recently read about Python one-liners that happens
to include a rather terse method of calculating the Fibonacci sequence for
the first N occurrences.

 

Since this is a somewhat education-oriented forum, let me explain a bit
before presenting it.

 

In the functools module there is a simple utility called reduce that takes
two or three arguments and uses them to sort of collapse an iterable into a
single value. I used it in an example yesterday to multiply all number
between K+1 and N as a possible way to shorten the calculation of
N!/((N-K)!K!)

 

The goal for Fibonacci is to give reduce a function and an iterable and a
starting point of [0, 1] and have it keep extending the list with the
remaining parts of the sequence by using several tricks. 

 

The first argument to reduce is a lambda function that takes two arguments
and IGNORES the second argument so an underscore placeholder is used. The
first argument will be a list of integers starting with [0, 1] but in later
iterations getting longer. The second argument, as mentioned, is irrelevant
as it is a sort of counter placeholder. Since x is a list you can reference
the last two elements and join them into a temporary list containing their
sum then append that list to the growing list of results:

 

(lambda x, _: x + [x[-2] + x[-1]]

 

Clear enough if a bit condensed and obscure at first?

 

So how do we get this to iterate enough times? For say 12 items when we
start with 2, we need 10 more. So we simply need N-2 iterations.

 

This nutty snippet produces a list with N-2 copies of 0 but what is relevant
is just that it is a list of length N-2:

 

[0] * (N-2)

 

So for N==12 this gives the list of [0,0,0,0,0,0,0,0,0,0]

 

Finally we tell reduce to begin with [0,1]

 

Here is the complete code:

 

from functools import reduce

 

N=12

 

N_fibs = reduce(lambda x, _: x + [x[-2] + x[-1]], [0] * (N-2), [0, 1])

 

When I run the above, I get:

 

>>> N_fibs

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

 

Of course you can change N, wrap it as a function and so on, and it works.
You can let the starting condition be another pair of numbers and make other
related sequences.

 

And is this the fastest or cheapest or even most comprehensible way? Nah!
And if the requester hands this in, the instructor may have some concerns on
.

 



More information about the Tutor mailing list