Tutorials 1 List & Sets.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction to Lists and Sets\n",
    "\n",
    "This is part of a tutorial on python basic objects.\n",
    "\n",
    "Authors: ['Arthur de Fluiter', 'Cheng-yu Lam']\n",
    "\n",
    "This particular document deals with python's `list` and `set`. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# List\n",
    "\n",
    "In Python, a list is \n",
    " - *dynamic* a list may grow and shrink. \n",
    " - *ordered* the elements added first are in the list first\n",
    " - *non-type specific* any element can be of a different type\n",
    " - *expensive to query* if you want to know whether something is in a list, you'll have to go through all elements\n",
    " - *cheap to store* relative to other structures, the list is fairly cheap in memory"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Creating an empty list can be done in the following ways\n",
    "empty_list = list()\n",
    "empty_list = []\n",
    "\n",
    "# A list of strings\n",
    "string_list = [\"apple\", \"orange\", \"banana\"]\n",
    "\n",
    "# A list of numbers\n",
    "number_list = [1, 1, 2, 2, 3, 42, 50, 100, 99999]\n",
    "\n",
    "# A list of varying types\n",
    "varying_list = [\"not\", 24, \"specified\", \"what\", \"type\", True]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Length of a list\n",
    "\n",
    "To get the length/size of a list, you can use `len(list)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length of the number list: 9\n"
     ]
    }
   ],
   "source": [
    "print(\"The length of the number list: %s\" % len(number_list))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Add an item to a list\n",
    "\n",
    "To add to an existing list, you can use the `append()` function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test = [1,2,3]\n",
    "test.append(4)\n",
    "test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Add multiple items to a list\n",
    "\n",
    "Additionally you sometimes want to add multiple elements to a list, this can be done via the `extend()` function.\n",
    "\n",
    "This function takes any 'iterable' object, this means any object you can loop over, like:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, -1, -2, -3]\n",
      "[1, 2, 3, -1, -2, -3, 0, 1, 2, 3, 4]\n",
      "[1, 2, 3, -1, -2, -3, 0, 1, 2, 3, 4, 'a', 'b', 'c']\n"
     ]
    }
   ],
   "source": [
    "test = [1,2,3]\n",
    "test.extend([-1, -2, -3]) # a list\n",
    "print(test)\n",
    "test.extend(range(5))     # a range\n",
    "print(test)\n",
    "test.extend(\"abc\")        # tries to loop over the string, returning all letters\n",
    "print(test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Get an item from a list\n",
    "\n",
    "Lists are ordered by their index. The index starts from 0, so the first item has index 0, the second item has index 1, and so on.\n",
    "\n",
    "To get an item from a list, use `list[index_of_item]`, for example `list[0]`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The third item in the number list: 2\n"
     ]
    }
   ],
   "source": [
    "print(\"The third item in the number list: %s\" % number_list[2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Get multiple items from a list\n",
    "You can get multiple connected items from a list with the [slice notation](https://docs.python.org/3.5/tutorial/introduction.html)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 2, 2, 3]\n",
      "[1, 1, 2, 2, 3]\n",
      "[42, 50, 100, 99999]\n"
     ]
    }
   ],
   "source": [
    "print(number_list[0:5])   # items from index 0 to 4 (5-1)\n",
    "print(number_list[:5])    # items from the beginning to index 4\n",
    "print(number_list[5:])    # items from index 5 to the end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Set an item in a list\n",
    "\n",
    "Similarly you can also set objects from a list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 1, 2, 3, 42, 50, 100, 99999]\n"
     ]
    }
   ],
   "source": [
    "# set a single element\n",
    "number_list[2] = 1\n",
    "print(number_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Set multple items in list\n",
    "\n",
    "You can also use the slice notation to assign part of the list (note that this is fairly slow, compared to append/extend)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 1, 2, 3, 42, 50, 100, 99999]\n",
      "[-1, -2, -3, 50, 100, 99999]\n"
     ]
    }
   ],
   "source": [
    "print(number_list)\n",
    "\n",
    "# set multiple elements (elements 0-5 are replaced with [-1,-2,-3])\n",
    "number_list[:6] = [-1, -2, -3]\n",
    "\n",
    "print(number_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## List comprehension\n",
    "\n",
    "List comprehension is a quick way create a list following an easy pattern.\n",
    "\n",
    "It makes the code shorter compared with for loops.\n",
    "\n",
    "We will use the number list above. Let's say we want to get a list from all numbers larger than 50. \n",
    "\n",
    "This is how one normally go about doing it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[100, 99999]\n"
     ]
    }
   ],
   "source": [
    "larger_than_50 = []\n",
    "for number in number_list:\n",
    "    if number > 50:\n",
    "        larger_than_50.append(number)\n",
    "        \n",
    "print(larger_than_50)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code below does the same thing:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[100, 99999]\n"
     ]
    }
   ],
   "source": [
    "larger_than_50_improved = [n for n in number_list if n > 50]\n",
    "print(larger_than_50_improved)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Note\n",
    "\n",
    "the structures in list comprehensions can become as complicated as you want, but you should not strive for this as it makes code harder to read.  \n",
    "\n",
    "The code below demonstrates this with a statement creating all sublists of a range. The resulting code becomes less readable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0], [1], [2], [3], [4], [5], [0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [0, 1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 5], [0, 1, 2, 3], [1, 2, 3, 4], [2, 3, 4, 5], [0, 1, 2, 3, 4], [1, 2, 3, 4, 5], [0, 1, 2, 3, 4, 5]]\n"
     ]
    }
   ],
   "source": [
    "nr = 6\n",
    "list_of_lists = [[x for x in range(start, start + size)] for size in range(1, nr+1) for start in range(nr) if start + size <= nr]\n",
    "print(list_of_lists)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sets\n",
    "\n",
    "Sets are:\n",
    "\n",
    "- *dynamic* sets can grow and shrink\n",
    "- *non-type specific* any element can be of a different type\n",
    "- *unordered* there is no fixed order in which you set or get elements\n",
    "- *uniqueness* every element is distinct, adding an element twice results in having the element only once\n",
    "- *cheap to query* opposite to lists, the operation to check whether an element is in a set is cheap\n",
    "- *expensive to store* sets require a lot of extra data, data structures are at times better stored as lists\n",
    "\n",
    "**Very important note**: \n",
    "\n",
    "Set literals (e.g. `a = {1,2,3}`) use the `{elem, ...}` notation, however curly brackets are also used for dicts. When the python people had to decide whether `{}` was an empty set or dict, they chose the latter. \n",
    "\n",
    "**This means an emtpy set cannot be written as `{}`.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2, 3, 100, 42, 50, 99999}\n"
     ]
    }
   ],
   "source": [
    "# Create an empty set\n",
    "empty_set = set() # DO NOT CONFUSE WITH {}, which gives a dict\n",
    "\n",
    "# A set of strings\n",
    "string_set = {\"apple\", \"orange\", \"banana\"}\n",
    "\n",
    "# A set of numbers\n",
    "number_set = {1, 1, 2, 2, 3, 42, 50, 100, 99999}\n",
    "\n",
    "# All the items in a set must be unique, duplicate items are eliminated\n",
    "print(number_set)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Length of a set\n",
    "Similar to a list, you use `len(set)` to find the length of a set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The length of the number set: 7\n"
     ]
    }
   ],
   "source": [
    "print(\"The length of the number set: %s\" % len(number_set))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Adding an item to a set\n",
    "\n",
    "Similar to the `list`'s  append, there is the `add()` function for the `set` which adds an element if it wasnt in there already"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{2, 3, 5}\n"
     ]
    }
   ],
   "source": [
    "primes = set()\n",
    "\n",
    "primes.add(2)\n",
    "primes.add(2)\n",
    "primes.add(3)\n",
    "primes.add(5)\n",
    "\n",
    "print(primes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Adding multiple items to a set\n",
    "\n",
    "Similar to the `list`s `extend` the set has `update` which adds everything from an `iterable` (think lists, ranges etc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "set()\n",
      "{1, 2, 3}\n",
      "{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}\n"
     ]
    }
   ],
   "source": [
    "numbers = set()\n",
    "\n",
    "print(numbers)\n",
    "\n",
    "numbers.update([1,2,3])\n",
    "\n",
    "print(numbers)\n",
    "\n",
    "numbers.update(range(10))\n",
    "\n",
    "print(numbers)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Getting item(s) from a set\n",
    "Since a set is not ordered, it is not possible to get an item from a set using an index. However, you can check if an item is in a set:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is 42 in the number set? Yes\n"
     ]
    }
   ],
   "source": [
    "print(\"Is 42 in the number set? %s\" % \"Yes\" if 42 in number_set else \"No\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Set comprehension\n",
    "Set comprehension is similar to list comprehension if you need to get part of a set according to some condition."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{100, 99999}\n",
      "{-3, -1, -2}\n",
      "[1, 2, 3, 42]\n"
     ]
    }
   ],
   "source": [
    "set_larger_than_50 = {n for n in number_set if n > 50}\n",
    "print(set_larger_than_50)\n",
    "\n",
    "# You can mix list comprehension and set comprehension\n",
    "print ({n for n in number_list if n < 50})    # A set from filtering a list\n",
    "print([n for n in number_set if n < 50])      # A list from filtering a set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Set Mathematical operators"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "S = {1,2,3,4}\n",
    "T = {2,3}\n",
    "U = {3,4,5,6}\n",
    "a = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In mathematics, sets have well defined operators namely the following:\n",
    "\n",
    "Is a in a set S\n",
    "\n",
    "$$\n",
    "a \\in S\n",
    "$$\n",
    "\n",
    "Or its python equivalent:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a in S"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Is T a subset of S\n",
    "\n",
    "$$\n",
    "T \\subset S\n",
    "$$\n",
    "\n",
    "and T is a subset or equals S\n",
    "\n",
    "$$\n",
    "T \\subseteq S\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "print(T <  S) # T is a subset of S\n",
    "print(S <  S) # S is not strictly a subset of S\n",
    "print(T <= S) # T still holds\n",
    "print(S <= S) # S is S, so this also holds"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly the supersets $\\supset$ and $\\supseteq$ work with the `>` and `>=` operators\n",
    "\n",
    "### `set` on `set` operations\n",
    "\n",
    "We also have the union operator for 2 sets, S and U\n",
    "$$\n",
    "S \\cup U\n",
    "$$\n",
    "\n",
    "![union](https://upload.wikimedia.org/wikipedia/commons/thumb/3/30/Venn0111.svg/320px-Venn0111.svg.png)\n",
    "\n",
    "And its equivalents"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2, 3, 4, 5, 6}\n",
      "{1, 2, 3, 4, 5, 6}\n"
     ]
    }
   ],
   "source": [
    "print(S.union(U))\n",
    "\n",
    "# or for short\n",
    "print(S | U)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Intersection of sets S and U\n",
    "$$\n",
    "S \\cap U\n",
    "$$\n",
    "\n",
    "![intersection](https://upload.wikimedia.org/wikipedia/commons/thumb/9/99/Venn0001.svg/320px-Venn0001.svg.png)\n",
    "\n",
    "and its python equivalents"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{3, 4}\n",
      "{3, 4}\n"
     ]
    }
   ],
   "source": [
    "print(S.intersection(U))\n",
    "\n",
    "# or for short\n",
    "print(S & U)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difference of S and U\n",
    "\n",
    "$$\n",
    "S \\setminus U\n",
    "$$\n",
    "\n",
    "![set](https://upload.wikimedia.org/wikipedia/commons/thumb/5/5a/Venn0010.svg/320px-Venn0010.svg.png)\n",
    "\n",
    "and its python equivalents"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2}\n",
      "{1, 2}\n"
     ]
    }
   ],
   "source": [
    "print(S.difference(U))\n",
    "\n",
    "#or for short\n",
    "print(S - U)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and symmetric difference of S and U\n",
    "\n",
    "![symmetric difference](https://upload.wikimedia.org/wikipedia/commons/thumb/4/46/Venn0110.svg/320px-Venn0110.svg.png)\n",
    "\n",
    "$$\n",
    "S \\bigtriangleup U\n",
    "$$\n",
    "\n",
    "And its python equivalent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 2, 5, 6}\n",
      "{1, 2, 5, 6}\n"
     ]
    }
   ],
   "source": [
    "# and the symmetric difference\n",
    "print(S.symmetric_difference(U))\n",
    "\n",
    "# or for short\n",
    "print(S ^ U)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}