Difference Fanout
Given a list of numbers, for each number generate a list of the differences between it and \(n_{fanout}\) (known as the fanout value) following numbers in the list. Return a list of all the lists generated for each number. For members in the list that have fewer than \(n_{fanout}\) following members, calculate as many differences as possible. For example, suppose we want to compute the difference fanout on the list [3, 2, 4, 6, 1] with a fanout value of 3. Then we would compute:
\(3 \rightarrow [2 - 3, 4 - 3, 6 - 3]\)
\(2 \rightarrow [4 - 2, 6 - 2, 1 - 2]\)
\(4 \rightarrow [6 - 4, 1 - 4]\)
\(6 \rightarrow [1 - 6]\)
\(1 \rightarrow []\)
# example behavior
>>> difference_fanout([3, 2, 4, 6, 1], 3)
[[-1, 1, 3], [2, 4, -1], [2, -3], [-5], []]
You will want to know about lists, indexing & slicing lists, and for-loops to solve this problem.
For extra credits (and some extra fun!), try to write your function only using list comprehension.
Solution: difference_fanout using for-loops
We will naturally tackle this problem by performing nested for-loops. The outermost for-loop will loop over each number in the list. We will refer to this number as the “base number”. We will want the inner for-loop to iterate ahead of the base number so that we can compute the differences between it and its \(n_{fanout}\) neighbors. We will need to take care re-initialize our intermediate list of differences for each new base number, otherwise each subtraction will get appended to one long list.
def difference_fanout(l, fanout):
""" Return a list of differences for
each value with its following terms
Parameters
----------
l: List[Number]
Input list of base numbers.
fanout: int
Number of neighbors to compute differences against.
Returns
-------
List[List[Number]]
"""
all_fanouts = [] # will store each list of fanouts
for i, base_number in enumerate(l):
# `base_fanout` will store the differences between
# the base number's successive neighbors and base number
base_fanout = []
for neighbor in l[i+1: i+1+fanout]:
base_fanout.append(neighbor - base_number)
all_fanouts.append(base_fanout)
return all_fanouts
Note our use of enumerate; this permits us to simultaneously access our base number, which we use in the subtraction, as well as its index-position within the list l, which we use to determine the neighbors.
Next, you may be concerned that our inner-loop will attempt to iterate beyond the end of the list. Consider the case in which base_number is the final element in l, thus l[i+1: i+1+fanout] would be equivalent to l[len(l): len(l)+fanout] - the stopping point for this slice clearly reaches beyond the extent of l (assuming fanout > 0). Fortunately, this is not an oversight on our part. While indexing a list outside of its bounds will raise an error, recall that a slice will
automatically limit itself to be within bounds of a given sequence. That is, l[i+1: i+1+fanout] actually behaves like l[min(i, len(l)-1): min(len(l), i+1+fanout)] (assuming we are dealing only with positive indices and non-empty lists). Thus our inner-loop will naturally limit itself. In the case that base_number is the final element in l, the inner-loop will exit
immediately, leaving base_fanout empty. Although somewhat obscure, this is an important aspect of Python’s slicing mechanism to keep in mind.
Solution: difference_fanout using list comprehensions
We can make judicious use of nested list comprehensions to simplify our solution. Although the syntax may appear to be convoluted at first glance, it permits us proceed without worrying about initializing multiple empty lists and appending to them at the right points in our nested for-loops
def difference_fanout(l, fanout):
""" Return a list of differences for
each value with its following terms
Parameters
----------
l: List[Number]
Input list
fanout: int
Number of neighbors to compute difference with
Returns
-------
List[Number]
"""
return [[neighbor - base for neighbor in l[i+1:i+1+fanout]]
for i,base in enumerate(l)]
See that the outermost list comprehension loops over the base number, as did the outer for-loop in the prior solution, and that the innermost list comprehension plays the same roll as the inner for-loop.
There are fewer potential points of failure in this solution, as its conciseness removes the “moving parts” that had to be managed in the previous solution. This should help demonstrate the power of the comprehension expression syntax.
Extension
Recall from earlier that functions are, under the hood, just objects with some special operations that allow you to “call” a function. This means that you can pass other functions as parameters into a function. It is especially powerful, since it enables us to generalize the purposes of our functions. For example, we don’t have to limit our function to just computing the difference between members and their following terms; we can apply any binary operation. Instead of finding the difference, we can calculate the sum or product or even concatenate two strings for a list of string. The possibilities are limitless.
Armed with this knowledge, we can generalize the code.
def apply_fanout(l, fanout, op):
""" Return a list of outputs for each value
after applying a binary operation between
the value and its following terms
Parameters
----------
l: List[Any]
Input list
fanout: int
Number of neighbors to apply the operation with
op: Callable[[Any, Any], Any]
Any binary operation to be applied to fanout-pairs
of elements in `l`.
Returns
-------
List[List[Any]]
"""
return [[op(neighbor, base) for neighbor in l[i+1:i+1+fanout]]
for i,base in enumerate(l)]
Now, we can rewrite difference_fanout simply as
def subtract(a, b):
return a - b
def difference_fanout(l, fanout):
return apply_fanout(l, fanout, subtract)
We can easily change subtract to some other function for a totally different use.