{ "cells": [ { "cell_type": "raw", "metadata": { "lines_to_next_cell": 2, "raw_mimetype": "text/restructuredtext" }, "source": [ ".. meta::\n", " :description: Topic: For-Loop Exercise, Difficulty: Easy, Category: Practice Problem\n", " :keywords: for loops, list, function, list comprehension, practice problem" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Difference Fanout\n", "\n", "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:\n", "\n", " - $3 \\rightarrow [2 - 3, 4 - 3, 6 - 3]$\n", " - $2 \\rightarrow [4 - 2, 6 - 2, 1 - 2]$\n", " - $4 \\rightarrow [6 - 4, 1 - 4]$\n", " - $6 \\rightarrow [1 - 6]$\n", " - $1 \\rightarrow []$\n", " \n", "``` Python\n", "# example behavior\n", ">>> difference_fanout([3, 2, 4, 6, 1], 3)\n", "[[-1, 1, 3], [2, 4, -1], [2, -3], [-5], []]\n", "```\n", "\n", "You will want to know about [lists](https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/Basic_Objects.html#Lists), [indexing & slicing](https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/SequenceTypes.html#Introducing-Indexing-and-Slicing) lists, and [for-loops](https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/ForLoops.html) to solve this problem.\n", "\n", "For extra credits (and some extra fun!), try to write your function only using [list comprehension](https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/Generators_and_Comprehensions.html#List-&-Tuple-Comprehensions). \n", "\n", "## Solution: difference_fanout using for-loops\n", "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. \n", "\n", "```python\n", "def difference_fanout(l, fanout):\n", " \"\"\" Return a list of differences for \n", " each value with its following terms\n", " \n", " Parameters\n", " ----------\n", " l: List[Number]\n", " Input list of base numbers.\n", " \n", " fanout: int\n", " Number of neighbors to compute differences against.\n", " \n", " Returns\n", " -------\n", " List[List[Number]]\n", " \"\"\"\n", " all_fanouts = [] # will store each list of fanouts\n", " for i, base_number in enumerate(l):\n", " # `base_fanout` will store the differences between \n", " # the base number's successive neighbors and base number\n", " base_fanout = [] \n", " for neighbor in l[i+1: i+1+fanout]:\n", " base_fanout.append(neighbor - base_number)\n", " \n", " all_fanouts.append(base_fanout)\n", " return all_fanouts\n", "```\n", "\n", "Note our use of [enumerate](https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/Iterables.html#Enumerating-iterables); 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. \n", "\n", "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](https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/SequenceTypes.html#Handling-out-of-bounds-indices). 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.\n", "\n", "## Solution: difference_fanout using list comprehensions\n", "We can make judicious use of nested [list comprehensions](https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/Generators_and_Comprehensions.html#List-&-Tuple-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\n", "\n", "``` Python\n", "def difference_fanout(l, fanout):\n", " \"\"\" Return a list of differences for \n", " each value with its following terms\n", " \n", " Parameters\n", " ----------\n", " l: List[Number]\n", " Input list\n", " \n", " fanout: int\n", " Number of neighbors to compute difference with\n", " \n", " Returns\n", " -------\n", " List[Number]\n", " \"\"\"\n", " return [[neighbor - base for neighbor in l[i+1:i+1+fanout]] \n", " for i,base in enumerate(l)]\n", "```\n", "\n", "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.\n", "\n", "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. \n", "\n", "## Extension\n", "Recall from [earlier](https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/Functions.html#Functions-are-Objects) 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. \n", "\n", "Armed with this knowledge, we can generalize the code.\n", "```Python\n", "def apply_fanout(l, fanout, op):\n", " \"\"\" Return a list of outputs for each value \n", " after applying a binary operation between \n", " the value and its following terms\n", " \n", " Parameters\n", " ----------\n", " l: List[Any]\n", " Input list\n", " \n", " fanout: int\n", " Number of neighbors to apply the operation with\n", " \n", " op: Callable[[Any, Any], Any]\n", " Any binary operation to be applied to fanout-pairs\n", " of elements in `l`.\n", " \n", " Returns\n", " -------\n", " List[List[Any]]\n", " \"\"\"\n", " return [[op(neighbor, base) for neighbor in l[i+1:i+1+fanout]] \n", " for i,base in enumerate(l)]\n", "```\n", "Now, we can rewrite `difference_fanout` simply as\n", "``` Python\n", "def subtract(a, b): \n", " return a - b\n", "\n", "def difference_fanout(l, fanout):\n", " return apply_fanout(l, fanout, subtract)\n", "```\n", "We can easily change `subtract` to some other function for a totally different use. " ] } ], "metadata": { "jupytext": { "text_representation": { "extension": ".md", "format_name": "markdown", "format_version": "1.3", "jupytext_version": "1.13.6" } }, "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" } }, "nbformat": 4, "nbformat_minor": 4 }