docs/Module2_EssentialsOfPython/DataStructures_III_Sets_and_More.ipynb

{
 "cells": [
  {
   "cell_type": "raw",
   "id": "urban-wisconsin",
   "metadata": {
    "lines_to_next_cell": 2,
    "raw_mimetype": "text/restructuredtext"
   },
   "source": [
    ".. meta::\n",
    "   :description: Topic: Introduction to Sets, Difficulty: Medium, Category: Section\n",
    "   :keywords: set, complexity, comparison, union, intersection, membership, hashing, lookup, interview preparation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "unauthorized-patrol",
   "metadata": {},
   "source": [
    "# Data Structures (Part III): Sets & the Collections Module\n",
    "## The \"Set\" Data Structure\n",
    "The `set` type describes an *unordered* collection of *unique* objects. It is useful for:\n",
    "\n",
    "- Filtering out \"repeat\" objects in a collection, producing only its unique members.\n",
    "- Quickly checking for membership, as a $\\mathcal{O}(1)$ operation.\n",
    "- Efficiently comparing two sets of objects; e.g. if one set is a \"subset\" of another.\n",
    "\n",
    "A set uses a \"hashing\" scheme for keeping track of its contents. Thus, like a dictionary's keys, a set can only store *immutable* objects so that its hashes will never become invalid. Unlike the other data structures that we have encountered, *there is no mechanism for retrieving an individual item from a set*. That is, there is no index or key that can be used to retrieve an individual member from a set. \n",
    "\n",
    "Python's sets also support many familiar set-algebra operations, like taking the union or intersection of sets, as we will see below. For an exhaustive listing of the functions available to sets, please consult [the official documentation on sets](https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "engaging-height",
   "metadata": {},
   "source": [
    "### Creating a set\n",
    "You can initialize a set using the syntax: `{item1, item2, ...}`. Please note that this is distinct from the the dictionary-initialization syntax, which uses a colon to indicate key-value pairs:\n",
    "\n",
    "```python\n",
    "# initializing a set containing various immutable objects\n",
    ">>> {1, 3.4, \"apple\", False, (1, 2, 3)}\n",
    "{False, 1, (1, 2, 3), 3.4, 'apple'}\n",
    "```\n",
    "A set can be constructed using the generator-comprehension syntax:\n",
    "```python\n",
    "# initialization via set-comprehension\n",
    ">>> {i**2 for i in range(5) if i != 3}\n",
    "{0, 1, 4, 16}\n",
    "```\n",
    "\n",
    "And, like the `list`, `tuple`, and `dict` types, the `set` type can be used to construct a set from an iterable. Note that you must use `set()` if you want to create an empty set, using `{}` creates an empty *dictionary*:\n",
    "```python\n",
    "# introducing the `set` type\n",
    ">>> type({2, 4, 6})\n",
    "set\n",
    "\n",
    "# using `set` to consume an iterable to construct a set\n",
    ">>> set(range(4))\n",
    "{0, 1, 2, 3}\n",
    "\n",
    "# creating an empty set\n",
    ">>> set()  # specifying `{}` would create an empty *dictionary*\n",
    "set()\n",
    "```\n",
    "\n",
    "Redundant items are \"ignored\" when constructing or adding to a set. Thus *constructing a set is a great way to extract the unique items from a collection*: \n",
    "```python\n",
    "# filter repeat-items from a collection by feeding it into a set\n",
    ">>> x = [1, 2, 1, 2, 1, \"moo\", \"moo\"]\n",
    ">>> set(x)\n",
    "{1, 2, 'moo'}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "earned-european",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-info\">\n",
    "\n",
    "**Reading Comprehension: Set Creation**\n",
    "\n",
    "Use a set to find all of the unique letters in the string `\"The cat in the hat\"`. Ignore all non-letter characters and lowercase all letters.\n",
    "\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aerial-raising",
   "metadata": {},
   "source": [
    "### Set operations\n",
    "Sets support membership-checking ($\\mathcal{O}(1)$) along with iteration ($\\mathcal{O}(n)$). Note that sets are unordered; thus the order of iteration is effectively random:\n",
    "```python\n",
    "# checking membership in a set\n",
    ">>> 2 in {1, 2, 3}\n",
    "True\n",
    "\n",
    "# iterating over a set (the order of iteration is random)\n",
    ">>> [i for i in {\"a\", \"b\", \"c\"}]\n",
    "['b', 'c', 'a']\n",
    "```\n",
    "Python also provides the set-theoretic operations of union, intersection, and the relations of set equality and set inclusion. These can be invoked using operator symbols or by calling functions on the set explicitly. \n",
    "\n",
    "For an exhaustive list of the functions available to the set, please [refer to the official Python documentation](https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset).\n",
    "\n",
    "```python\n",
    "# demonstrating set-comparison operations\n",
    ">>> x = {\"a\", \"b\", \"c\", \"d\"}\n",
    ">>> y = {\"a\", \"b\", \"e\"}\n",
    "\n",
    "# union: items in x or y, or both\n",
    ">>> x | y  # or x.union(y)\n",
    "{'a', 'b', 'c', 'd', 'e'}\n",
    "\n",
    "# intersection: items in both x and y\n",
    ">>> x & y  # or x.intersection(y)\n",
    "{'a', 'b'}\n",
    "\n",
    "# difference: items in x but not in y\n",
    ">>> x - y  # or x.difference(y)\n",
    "{'c', 'd'}\n",
    "\n",
    "# symmetric difference: in x or y, but not in both\n",
    ">>> x ^ y  # or x.symmetric_difference\n",
    "{'c', 'd', 'e'}\n",
    "\n",
    "# check if set_1 is a superset of set_2\n",
    ">>> {1, 2, 3, 4} >= {1, 2}\n",
    "True\n",
    "\n",
    "# check if set_1 and set_2 are equivalent sets\n",
    ">>> {1, 2, 3, 4} == {1, 2}\n",
    "False\n",
    "```\n",
    "\n",
    "A set is a *mutable* object; it can be updated after it was created:\n",
    "```python\n",
    "# sets are mutable\n",
    "\n",
    "# add a single member to `x`\n",
    ">>> x.add(\"dog\")\n",
    "\n",
    "# update `x` by adding members of an iterable\n",
    ">>> x.update([1, 2, 3])\n",
    "\n",
    "# remove a member of `x`\n",
    ">>> x.remove(\"a\")\n",
    ">>> x\n",
    "{1, 2, 3, 'b', 'c', 'd', 'dog'}\n",
    "```\n",
    "Because it is mutable, a set cannot be used as a dictionary-key, nor can a set be a member of another set. Python provides an immutable version of the set, `frozenset`, which has all of the functions of a set other than those that mutate the set:\n",
    "```python\n",
    "# `frozenset` is an immutable version of a Python set\n",
    ">>> frozenset(x)\n",
    "frozenset({1, 2, 3, 'b', 'c', 'd', 'dog'})\n",
    "```\n",
    "\n",
    "<div class=\"alert alert-info\"> \n",
    "\n",
    "**Takeaway**: \n",
    "\n",
    "Python's set is an unordered collection of unique, immutable objects. It is an excellent tool for extracting the unique members from a collection of items. The set provides  $\\mathcal{O}(1)$ membership-checking along with a suite of set-algebra operations for comparing sets. `frozenset` is an immutable version of the set.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "correct-compound",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-info\">\n",
    "\n",
    "**Reading Comprehension: Set Comparisons**\n",
    "\n",
    "Given the enrollment lists for class-A and class-B, find the students enrolled in both classes. Produce the result as a sorted list of names. \n",
    "\n",
    "```python\n",
    ">>> classA = [\"Bohr\", \"Curie\", \"David\", \"Euler\", \"Fermi\", \"Feynman\", \"Gauss\", \"Heisenberg\", \"Noether\"]\n",
    ">>> classB = [\"Bohm\", \"Bohr\", \"Einstein\", \"Fermi\", \"Gauss\", \"Hopper\", \"Montalcini\"]  \n",
    "```\n",
    "\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dying-contractor",
   "metadata": {},
   "source": [
    "## The Collections Module\n",
    "Python provides a number of valuable, optimized data structures in its [\"collections\" module](https://docs.python.org/3/library/collections.html). It is recommended that the reader take some time to peruse this module. Here, we will briefly show off some of the utilities of its data structures. \n",
    "\n",
    "Refer to the [official documentation](https://docs.python.org/3/library/collections.html) for a complete listing of the functions available to these data structures."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "acoustic-gnome",
   "metadata": {},
   "source": [
    "### Named-Tuple\n",
    "A named tuple allows you to form a tuple whose members are named. Thus the user can access a member by name or via index. Otherwise the named tuple behaves just like a typical tuple. This facilitates clean, readable code.\n",
    "\n",
    "Suppose, for instance, you want to keep track of the 3D-position and time of an event. You can use a named-tuple so that each space and time coordinate can be referenced \"by name\". In this way, the reader doesn't have to keep in mind that element-3 of your tuple corresponds to time:\n",
    "\n",
    "```python\n",
    "# demonstrate the use of named tuple\n",
    ">>> from collections import namedtuple\n",
    "\n",
    "# Define a tuple that holds a space-time coordinate.\n",
    "# Here we define the tuple to have four entries, named \n",
    "# 'x', 'y', 'z', and 't', in order.\n",
    ">>> space_time_coord = namedtuple(\"space_time_coord\", ['x', 'y', 'z', 't'])\n",
    "\n",
    "# `r` is a particular space-time coordinate (an instance of our named tuple)\n",
    ">>> r = space_time_coord(1.5, 2.3, 5.1, 100.2)\n",
    "\n",
    ">>> r.x  # access the x coordinate \"by name\"; this is more descriptive than `r[0]`\n",
    "1.5\n",
    "\n",
    ">>> r.y\n",
    "2.3\n",
    "\n",
    ">>> r.z\n",
    "5.1\n",
    "\n",
    ">>> r.t  \n",
    "100.2\n",
    "\n",
    "# you can also access contents by indexing/slicing\n",
    ">>> r[3]  \n",
    "100.2\n",
    "\n",
    ">>> r[:]\n",
    "(1.5, 2.3, 5.1, 100.2)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "sporting-diabetes",
   "metadata": {},
   "source": [
    "### Default Dictionary\n",
    "A default dictionary allows you to specify a Python function, $f$ that will be used as a \"default value\" for that dictionary. The default value will be whatever $f()$ returns. That is, whenever you try to access a key that does not exist in the dictionary, instead of raising `KeyError`, the mapping $key \\rightarrow f()$ will be created in the dictionary:\n",
    "\n",
    "```python\n",
    "# demonstrate the behavior of the `defaultdict`\n",
    ">>> from collections import defaultdict\n",
    "\n",
    ">>> example_default_dict = defaultdict(list)  # will map any missing key to `list()`\n",
    ">>> example_default_dict  # an empty default dictionary\n",
    "defaultdict(list, {})\n",
    "\n",
    "# \"apple\" is not a key, so the default mapping \"apple\" -> list() is created\n",
    "# and this value is returned\n",
    ">>> example_default_dict[\"apple\"]  \n",
    "[]\n",
    "\n",
    "# this mapping now exists in the dictionary\n",
    ">>> example_default_dict \n",
    "defaultdict(list, {'apple': []})\n",
    "```\n",
    "\n",
    "Suppose you want to use a dictionary as a grade book, which maps $name \\rightarrow grades$. With a standard dictionary, you have to worry about encountering a student for the first time:\n",
    "```python\n",
    "# using a vanilla dictionary to store: name -> list of grades\n",
    "student = \"Ryan\"\n",
    "grade = 52  # I failed the test...\n",
    "\n",
    "# standard dictionary usage\n",
    "gradebook = {}\n",
    "\n",
    "# if student isn't in the gradebook, enter that student \n",
    "# along with an empty list as the grades\n",
    "if student not in gradebook:\n",
    "    gradebook[student] = []\n",
    "\n",
    "gradebook[student].append(grade)  # append the grade to that student's list of grades\n",
    "```\n",
    "The default dictionary's behavior exactly accommodates this initialization process (when providing `list` as the initialization function):\n",
    "\n",
    "```python\n",
    "# using a default dictionary to store: name -> list of grades\n",
    ">>> gradebook = defaultdict(list)\n",
    "\n",
    "# Because \"Susan\" doesn't exist in the dictionary\n",
    "# `list()` creates an empty list, as a default value,\n",
    "# which we can immediately append her grade to\n",
    ">>> gradebook[\"Susan\"].append(84)\n",
    "\n",
    ">>> gradebook\n",
    "defaultdict(list, {'Susan': [84]})\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "secondary-default",
   "metadata": {},
   "source": [
    "### Counter\n",
    "Python's counter data structure is designed for tallying the unique objects that it encounters. It essentially creates a dictionary that maps: $obj \\rightarrow count$. Suppose you want to study the distribution of words used in a body of text; counter is perfect for this application:\n",
    "```python\n",
    "# demonstrate the `Counter` data structure\n",
    ">>> from collections import Counter\n",
    "\n",
    "# Note: We will \"normalize\" our text by making it all lowercase. \n",
    "# We will then split the string by its spaces, storing the resulting \n",
    "# tokens in a list. For real text, we would also want to remove punctuation\n",
    ">>> text_1 = \"The cat in the hat\"\n",
    ">>> text_1 = text_1.lower().split()\n",
    ">>> text_1\n",
    "['the', 'cat', 'in', 'the', 'hat']\n",
    "\n",
    ">>> word_distr = Counter(text_1)  # tally the unique objects in `text_1`\n",
    ">>> word_distr\n",
    "Counter({'cat': 1, 'hat': 1, 'in': 1, 'the': 2})\n",
    "\n",
    "# feed additional items to the counter by \"update\"\n",
    ">>> text_2 = \"The apple in the tree\"\n",
    ">>> text_2 = text_2.lower().split()\n",
    ">>> word_distr.update(text_2)\n",
    ">>> word_distr\n",
    "Counter({'apple': 1, 'cat': 1, 'hat': 1, 'in': 2, 'the': 4, 'tree': 1})\n",
    "\n",
    "# get the top-2 most common words, along with their counts\n",
    ">>> word_distr.most_common(2)\n",
    "[('the', 4), ('in', 2)]\n",
    "\n",
    "# get the count for the word \"tree\"\n",
    ">>> word_distr[\"tree\"]\n",
    "1\n",
    "```\n",
    "\n",
    "`Counter` accepts any iterable of immutable objects:\n",
    "```python\n",
    ">>> Counter([0, 0, \"moo\", (None, None), (None, None), (None, None)])\n",
    "Counter({(None, None): 3, 0: 2, 'moo': 1})\n",
    "```\n",
    "Refer to the [official documentation](https://docs.python.org/3/library/collections.html#counter-objects) for a complete listing of all the nice functions that `Counter` has access to."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "attractive-florist",
   "metadata": {},
   "source": [
    "### The deque\n",
    "Like the list, Python's deque is a mutable, sequential data structure. What distinguishes the deque is that:\n",
    "\n",
    " - Mutating either the beginning or the end of a deque is $\\mathcal{O}(1)$, whereas mutating the beginning of a list is $\\mathcal{O}(n)$. As such, the deque has unique functions to take advantage of this, like `appendleft`.\n",
    " - The downside of the preceding feature is that *accessing items near the middle of the deque is* $\\mathcal{O}(n)$, whereas it is $\\mathcal{O}(1)$ for lists and tuples.\n",
    "\n",
    "A complete rundown of the deque's functionality can be found [here](https://docs.python.org/3/library/collections.html#deque-objects).\n",
    "\n",
    "The deque is included in Python's `collections` module, and thus must be imported:\n",
    "```python\n",
    ">>> from collections import deque\n",
    ">>> my_deque = deque([1,2,3])\n",
    ">>> my_deque.appendleft(0)\n",
    ">>> my_deque\n",
    "deque([0, 1, 2, 3])\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "jewish-fortune",
   "metadata": {},
   "source": [
    "## Links to Official Documentation\n",
    "\n",
    "- [Sets and frozen sets](https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset)\n",
    "  - [Tutorial on sets](https://docs.python.org/3/tutorial/datastructures.html#sets)\n",
    "- [The collections module](https://docs.python.org/3/library/collections.html)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "happy-remainder",
   "metadata": {},
   "source": [
    "## Reading Comprehension Solutions"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "sudden-semester",
   "metadata": {},
   "source": [
    "**Set Creation: Solution**\n",
    "\n",
    "Use a set to find all of the unique letters in the string `\"The cat in the hat\"`. Ignore all non-letter characters and lowercase all letters.\n",
    "\n",
    "We can use the built-in string functions [isalpha](https://docs.python.org/3/library/stdtypes.html#str.isalpha) and [lower](https://docs.python.org/3/library/stdtypes.html#str.lower) to filter out non-letter characters, and to lowercase the letters.\n",
    "\n",
    "```python\n",
    ">>> sentence = \"The cat in the hat\"\n",
    ">>> {char.lower() for char in sentence if char.isalpha()}\n",
    "{'a', 'c', 'e', 'h', 'i', 'n', 't'}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "hundred-worthy",
   "metadata": {},
   "source": [
    "**Set Comparisons: Solution**\n",
    "\n",
    "Given the roster for class-A and class-B, find the students enrolled in both classes. Produce the result as a sorted list.\n",
    "\n",
    "```python\n",
    ">>> classA = [\"Bohr\", \"Curie\", \"David\", \"Euler\", \"Fermi\", \"Feynman\", \"Gauss\", \"Heisenberg\", \"Noether\"]\n",
    ">>> classB = [\"Bohm\", \"Bohr\", \"Einstein\", \"Fermi\", \"Gauss\", \"Hopper\", \"Montalcini\"]  \n",
    "```\n",
    "We can find the entries common to both lists by constructing sets from them, and then taking the intersection of those sets. The result is a set,  which is an iterable. Thus it can be fed to the built-in function [sorted](https://www.pythonlikeyoumeanit.com/Module2_EssentialsOfPython/Iterables.html#Functions-that-act-on-iterables), to produce a sorted list of names.\n",
    "\n",
    "```python\n",
    ">>> sorted(set(classA) & set(classB))\n",
    "['Bohr', 'Fermi', 'Gauss']\n",
    "```"
   ]
  }
 ],
 "metadata": {
  "jupytext": {
   "text_representation": {
    "extension": ".md",
    "format_name": "markdown",
    "format_version": "1.2",
    "jupytext_version": "1.9.1"
   }
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}