itertools.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import itertools\n",
    "import operator\n",
    "import sys\n",
    "import numpy as np\n",
    "from collections import defaultdict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Itertools Module\n",
    "### Part of the standard Python library\n",
    "### import itertools\n",
    "### The module standardizes a core set of fast, memory efficient tools that are useful by themselves or in combination"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Why is it called itertools? \n",
    "### It has consists of functions made using iterator building blocks \n",
    "### Iterators are a more general type of structure than generators. Every generator is an iterator but not every iterator is a generator.  \n",
    "### All of the functions in the itertools module have yield keyword"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What is a generator?\n",
    "### It is a python object returned by a function calling keyword yield\n",
    "### An object sitting in memory with a function, ready for you to ask it for a value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def square(nums): \n",
    "    for num in nums:\n",
    "        yield num ** 2   # yield makes it a generator function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<generator object square at 0x107469e60>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,2,3,4,5]\n",
    "square(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def square1(nums):\n",
    "    results = []\n",
    "    for num in nums:\n",
    "        results.append(num**2)\n",
    "    return results      # normal function uses return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 4, 9, 16, 25]\n"
     ]
    }
   ],
   "source": [
    "nums = [1,2,3,4,5]\n",
    "result = square1(nums)\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### List Comprehension"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 2, 4, 6, 8]\n"
     ]
    }
   ],
   "source": [
    "lst = [x * 2 for x in range(5)]\n",
    "print(lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Generator expression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<generator object <genexpr> at 0x1074e3048>\n"
     ]
    }
   ],
   "source": [
    "gen = (x * 2 for x in range(5))\n",
    "print(gen)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ways to get output from a generator\n",
    "### next( )\n",
    "### for-loop\n",
    "### convert to tuple or list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "ename": "StopIteration",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mStopIteration\u001b[0m                             Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-13-8a6233884a6c>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mnext\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgen\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mStopIteration\u001b[0m: "
     ]
    }
   ],
   "source": [
    "next(gen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "result = (x * 2 for x in range(5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "2\n",
      "4\n",
      "6\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "for num in result: # the for-loop knows when the generator is exhausted and doesn't get a StopIteration error\n",
    "    print(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "result = (x * 2 for x in range(5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, 2, 4, 6, 8)"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tuple(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "result = (x * 2 for x in range(5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 2, 4, 6, 8]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Why generators?\n",
    "### 1. Speed\n",
    "### 2. Memory\n",
    "### Generators don't hold the entire result in memory. They yield one result at a time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "one_million = 1000000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def make_list(size):\n",
    "    return list(range(size))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def make_np_array(size):\n",
    "    return np.arange(size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def make_generator(size):\n",
    "    for num in range(size):\n",
    "        yield num"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Millisecond (ms): 10^-3 seconds   ---> 0.001              seconds\n",
    "### Microsecond (µs): 10^-6 seconds ---> 0.000001        seconds\n",
    "### Nanosecond (ns): 10^-9 seconds  ---> 0.000000001  seconds"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "List timeit:\n",
      "39.9 ms ± 1.03 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "print('List timeit:') \n",
    "%timeit make_list(one_million)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Numpy array timeit:\n",
      "2.38 ms ± 112 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "print('Numpy array timeit:') \n",
    "%timeit make_np_array(one_million)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Generator timeit:\n",
      "369 ns ± 18.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)\n"
     ]
    }
   ],
   "source": [
    "print('Generator timeit:') \n",
    "%timeit make_generator(one_million)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size of list: 9000112 bytes\n"
     ]
    }
   ],
   "source": [
    "lst = list(range(one_million))\n",
    "print('Size of list:', sys.getsizeof(lst), 'bytes')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size of numpy array: 8000096 bytes\n"
     ]
    }
   ],
   "source": [
    "np_array = np.arange(one_million)\n",
    "print('Size of numpy array:', sys.getsizeof(np_array), 'bytes')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size of generator: 88 bytes\n"
     ]
    }
   ],
   "source": [
    "gen = (x for x in range(one_million))\n",
    "print('Size of generator:', sys.getsizeof(gen), 'bytes')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Infinite Iterators  \n",
    "\n",
    "### Need to break out of these or they will iterate infinitely.\n",
    "### Useful for generating numbers or cycling over iterables of unknown length."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## count(start=0, step=1)\n",
    "### evenly spaced values from start"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "11\n",
      "12\n",
      "13\n",
      "14\n",
      "15\n",
      "16\n",
      "17\n",
      "18\n",
      "19\n"
     ]
    }
   ],
   "source": [
    "for num in range(10, 20): # normal way\n",
    "    print(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "11\n",
      "12\n",
      "13\n",
      "14\n",
      "15\n",
      "16\n",
      "17\n",
      "18\n",
      "19\n"
     ]
    }
   ],
   "source": [
    "for num in itertools.count(10): # itertools way\n",
    "    if num == 20:\n",
    "        break\n",
    "    else:\n",
    "        print(num)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### I can still access these one at time using next "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "results = itertools.count(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "next(results)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## cycle(iterable)\n",
    "### cycle through a series of values infinitely"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "words = ['foo', 'bar']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "foo\n",
      "bar\n",
      "foo\n",
      "bar\n",
      "foo\n",
      "bar\n",
      "foo\n",
      "bar\n",
      "foo\n",
      "bar\n"
     ]
    }
   ],
   "source": [
    "count = 0\n",
    "for word in itertools.cycle(words):\n",
    "    if count == 10:\n",
    "        break\n",
    "    print(word)\n",
    "    count +=1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## islice(iterable, stop)\n",
    "## islice(iterable, start, stop[, step])\n",
    "### used to slice iterables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "lst = [0,1,2,3,4,5,6,7,8,9]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<itertools.islice at 0x107528318>"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "itertools.islice(lst, 6) # similar to normal list slicing but, it is an iterator object"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### To access the elements in this object, use next( ), a for-loop, or convert to a list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "for num in itertools.islice(lst, 6):\n",
    "    print(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "5\n",
      "6\n",
      "7\n"
     ]
    }
   ],
   "source": [
    "for num in itertools.islice(lst, 4, 8):\n",
    "    print(num)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Combine with count( ) to get a slice of the infinite counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "11\n",
      "12\n",
      "13\n",
      "14\n",
      "15\n"
     ]
    }
   ],
   "source": [
    "for num in itertools.islice(itertools.count(10), 6): # count infinitely, starting from 10\n",
    "    print(num)                                       # take a slice of the infinite count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bringing back the cycle function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "words = ['foo', 'bar']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "foo\n",
      "bar\n",
      "foo\n",
      "bar\n",
      "foo\n",
      "bar\n",
      "foo\n",
      "bar\n",
      "foo\n",
      "bar\n"
     ]
    }
   ],
   "source": [
    "count = 0\n",
    "for word in itertools.cycle(words):\n",
    "    if count == 10:\n",
    "        break\n",
    "    print(word)\n",
    "    count +=1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Combine with islice( ) to get a portion of the infinite cycle and to make code shorter "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "foo\n",
      "bar\n",
      "foo\n",
      "bar\n",
      "foo\n",
      "bar\n",
      "foo\n",
      "bar\n",
      "foo\n",
      "bar\n"
     ]
    }
   ],
   "source": [
    "for word in itertools.islice(itertools.cycle(words), 10):      # cycle infinitely\n",
    "    print(word)                                                # take a slice of the infinite cycle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Check memory usage of islice object"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "one_million = 1000000\n",
    "lst = list(range(one_million))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<itertools.islice at 0x1075780e8>"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "islice = itertools.islice(lst, one_million)\n",
    "islice"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size of itertools.islice object: 80 bytes\n"
     ]
    }
   ],
   "source": [
    "print('Size of itertools.islice object:', sys.getsizeof(islice), 'bytes')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Iterators that terminate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## accumulate(iterable[, func])  \n",
    "### Make an iterator that returns accumulated sums, or accumulated results of other binary functions (specified via the optional func argument). If func is supplied, it should be a function of two arguments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### accumulate( ) uses operator.sum as its default function. \n",
    "### The operator module takes standard operators and makes them into functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "3\n",
      "6\n",
      "10\n",
      "15\n",
      "21\n",
      "28\n",
      "36\n",
      "45\n"
     ]
    }
   ],
   "source": [
    "for num in itertools.accumulate(nums):        # this returns a running total\n",
    "    print(num)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Use operator.mul in the func argument to get running product"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "0\n",
      "0\n",
      "0\n",
      "0\n",
      "0\n",
      "0\n",
      "0\n",
      "0\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "for num in itertools.accumulate(nums, operator.mul): \n",
    "    print(num)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Why are we getting all zeros? Our list starts with zero. The first product is zero and continues for the entire list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "nums = [1,2,3,4,5,6,7,8,9,10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "6\n",
      "24\n",
      "120\n",
      "720\n",
      "5040\n",
      "40320\n",
      "362880\n",
      "3628800\n"
     ]
    }
   ],
   "source": [
    "for num in itertools.accumulate(nums, operator.mul):\n",
    "    print(num)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### We get factorials\n",
    "### How do we get a single factorial?  \n",
    "### Use islice!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## islice(iterable, start, stop[, step])\n",
    "## accumulate(iterable[, func])  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "30414093201713378043612608166064768844377641568960512000000000000\n"
     ]
    }
   ],
   "source": [
    "nums = list(range(1, 100))\n",
    "for num in itertools.islice(itertools.accumulate(nums, operator.mul), 49, 50): #50th factorial, need the 49th element\n",
    "    print(num)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## chain.from_iterable(iterable)\n",
    "### takes an interable and flattens it into one long iterable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "nested = ((1,2,3),(1,2,3),(1,2,3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 2, 3, 1, 2, 3, 1, 2, 3)\n"
     ]
    }
   ],
   "source": [
    "flat = itertools.chain.from_iterable(nested)\n",
    "print(tuple(flat))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## product(*iterables, repeat=1)\n",
    "### Cartesian product of input iterables.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### cartesian product is the set of all combinations of the items"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### \\*args and \\**kwargs allow you to pass a variable number of arguments to a function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "nums = [1, 2, 3]\n",
    "fruit = ['apple', 'banana', 'orange']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tuple(itertools.product(nums, fruit))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "vegetables = ['carrots', 'peas', 'spinach']\n",
    "tuple(itertools.product(nums, fruit, vegetables))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### All playing card combinations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(('2', 'C'),\n",
       " ('2', 'D'),\n",
       " ('2', 'H'),\n",
       " ('2', 'S'),\n",
       " ('3', 'C'),\n",
       " ('3', 'D'),\n",
       " ('3', 'H'),\n",
       " ('3', 'S'),\n",
       " ('4', 'C'),\n",
       " ('4', 'D'),\n",
       " ('4', 'H'),\n",
       " ('4', 'S'),\n",
       " ('5', 'C'),\n",
       " ('5', 'D'),\n",
       " ('5', 'H'),\n",
       " ('5', 'S'),\n",
       " ('6', 'C'),\n",
       " ('6', 'D'),\n",
       " ('6', 'H'),\n",
       " ('6', 'S'),\n",
       " ('7', 'C'),\n",
       " ('7', 'D'),\n",
       " ('7', 'H'),\n",
       " ('7', 'S'),\n",
       " ('8', 'C'),\n",
       " ('8', 'D'),\n",
       " ('8', 'H'),\n",
       " ('8', 'S'),\n",
       " ('9', 'C'),\n",
       " ('9', 'D'),\n",
       " ('9', 'H'),\n",
       " ('9', 'S'),\n",
       " ('10', 'C'),\n",
       " ('10', 'D'),\n",
       " ('10', 'H'),\n",
       " ('10', 'S'),\n",
       " ('A', 'C'),\n",
       " ('A', 'D'),\n",
       " ('A', 'H'),\n",
       " ('A', 'S'),\n",
       " ('K', 'C'),\n",
       " ('K', 'D'),\n",
       " ('K', 'H'),\n",
       " ('K', 'S'),\n",
       " ('Q', 'C'),\n",
       " ('Q', 'D'),\n",
       " ('Q', 'H'),\n",
       " ('Q', 'S'),\n",
       " ('J', 'C'),\n",
       " ('J', 'D'),\n",
       " ('J', 'H'),\n",
       " ('J', 'S'))"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "suits = list('CDHS') # list of 4 suits \n",
    "ranks = [str(x) for x in range(2,11)] + list('AKQJ') # list of 13 ranks\n",
    "tuple(itertools.product(ranks,suits)) # set of all ordered pairs "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### All dice combinations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((1, 1),\n",
       " (1, 2),\n",
       " (1, 3),\n",
       " (1, 4),\n",
       " (1, 5),\n",
       " (1, 6),\n",
       " (2, 1),\n",
       " (2, 2),\n",
       " (2, 3),\n",
       " (2, 4),\n",
       " (2, 5),\n",
       " (2, 6),\n",
       " (3, 1),\n",
       " (3, 2),\n",
       " (3, 3),\n",
       " (3, 4),\n",
       " (3, 5),\n",
       " (3, 6),\n",
       " (4, 1),\n",
       " (4, 2),\n",
       " (4, 3),\n",
       " (4, 4),\n",
       " (4, 5),\n",
       " (4, 6),\n",
       " (5, 1),\n",
       " (5, 2),\n",
       " (5, 3),\n",
       " (5, 4),\n",
       " (5, 5),\n",
       " (5, 6),\n",
       " (6, 1),\n",
       " (6, 2),\n",
       " (6, 3),\n",
       " (6, 4),\n",
       " (6, 5),\n",
       " (6, 6))"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = range(1,7)\n",
    "b = range(1,7)\n",
    "tuple(itertools.product(a,b))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## combinations(iterable, r)\n",
    "### Return r length subsequences of elements from the input iterable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "salad = ('apples', 'beets', 'carrots', 'dates', 'escarole')\n",
    "tuple(itertools.combinations(salad, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## itertools.combinations_with_replacement(iterable, r)\n",
    "### Return r length subsequences of elements from the input iterable allowing individual elements to be repeated more than once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('chocolate', 'chocolate', 'chocolate')\n",
      "('chocolate', 'chocolate', 'strawberry')\n",
      "('chocolate', 'chocolate', 'vanilla')\n",
      "('chocolate', 'strawberry', 'strawberry')\n",
      "('chocolate', 'strawberry', 'vanilla')\n",
      "('chocolate', 'vanilla', 'vanilla')\n",
      "('strawberry', 'strawberry', 'strawberry')\n",
      "('strawberry', 'strawberry', 'vanilla')\n",
      "('strawberry', 'vanilla', 'vanilla')\n",
      "('vanilla', 'vanilla', 'vanilla')\n"
     ]
    }
   ],
   "source": [
    "flavors = ('chocolate','strawberry','vanilla')\n",
    "for comb in itertools.combinations_with_replacement(flavors, 3):\n",
    "    print(comb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### To get all combinations, add a nested for-loop for the number of flavors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "flavors = ('chocolate','strawberry','vanilla')\n",
    "num_flavors = len(flavors)\n",
    "for n in range(num_flavors + 1):\n",
    "    for comb in itertools.combinations(flavors, n+1):\n",
    "        print(tuple(comb))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "flavors = ['chocolate','strawberry','vanilla']\n",
    "num_flavors = len(flavors)\n",
    "for n in range(num_flavors):\n",
    "    for comb in itertools.combinations_with_replacement(flavors, n+1):\n",
    "        print(tuple(comb))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## permutations(iterable, r)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ways to award gold, silver, bronze medals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('alice', 'bob', 'charlie')\n",
      "('alice', 'charlie', 'bob')\n",
      "('bob', 'alice', 'charlie')\n",
      "('bob', 'charlie', 'alice')\n",
      "('charlie', 'alice', 'bob')\n",
      "('charlie', 'bob', 'alice')\n"
     ]
    }
   ],
   "source": [
    "names = ['alice', 'bob', 'charlie']\n",
    "for comb in itertools.permutations(names, 3):\n",
    "    print(comb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fibonacci Numbers  \n",
    "### This is an infinite fibonacci loop. Use itertools to extract values!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fibonacci():\n",
    "    (a, b) = (0, 1) # initial assignment of a, b using tuple assignment with unpacking\n",
    "    while True:     # this makes it an infinite loop\n",
    "        yield a\n",
    "        (a, b) = (b, a + b)   # reset a and b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## itertools.islice(iterable, stop)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "1\n",
      "2\n",
      "3\n",
      "5\n",
      "8\n",
      "13\n",
      "21\n",
      "34\n",
      "55\n",
      "89\n",
      "144\n",
      "233\n",
      "377\n",
      "610\n",
      "987\n",
      "1597\n",
      "2584\n",
      "4181\n"
     ]
    }
   ],
   "source": [
    "for num in itertools.islice(fibonacci(), 20):\n",
    "    print(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875\n"
     ]
    }
   ],
   "source": [
    "for num in itertools.islice(fibonacci(), 1000, 1001): # 1000th fib number\n",
    "    print(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "80"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sys.getsizeof(itertools.islice(fibonacci(), 1000, 1001))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## More examples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## itertools.takewhile(predicate, iterable)\n",
    "### Make an iterator that returns elements from the iterable as long as the predicate is true.\n",
    "### predicate is a function that returns True or False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for num in itertools.takewhile(lambda x: x < 100, fibonacci()):\n",
    "    print(num)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## itertools.filterfalse(predicate, iterable)\n",
    "### Make an iterator that filters elements from iterable returning only those for which the predicate is False."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "0==False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "x % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "False == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "x % 2 == False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "for even nums: x % 2 returns 0, and 0 == False, so x % 2 evaluates to False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for num in itertools.islice((itertools.filterfalse(lambda x: x % 2, fibonacci())), 20): \n",
    "    print(num)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## itertools.tee(iterable, n=2)\n",
    "### Return n independent iterators from a single iterable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "gen1, gen2 = itertools.tee(islice(fibonacci(), n))\n",
    "for i in ifilterfalse(lambda x: x % 2, generator1):\n",
    "    print i\n",
    "for i in ifilter(lambda x: x % 2, generator2):\n",
    "    print i"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## itertools.compress(data, selectors)\n",
    "### Make an iterator that filters elements from data returning only those that have a corresponding element in selectors that evaluates to True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for num in itertools.compress(fibonacci(), [1,1,1,0,0,1,1,1,0,1]):\n",
    "    print(num)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## itertools.zip_longest(*iterables, fillvalue=None)\n",
    "### Make an iterator that aggregates elements from each of the iterables. If the iterables are of uneven length, missing values are filled-in with fillvalue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "foods = ['apple', 'banana', 'orange', 'broccoli', 'carrot', 'kale']\n",
    "nums = [1, 2, 3, 4, 5, 6, 7, 8, 9,10]\n",
    "for tup in itertools.zip_longest(foods, nums, fillvalue = None):\n",
    "    print(tup)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## itertools.starmap(function, iterable)\n",
    "### Make an iterator that computes the function using arguments obtained from the iterable. Used instead of map() when argument parameters are already grouped in tuples from a single iterable (the data has been “pre-zipped”).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tups = [(1, 2), (3, 4), (5, 6)]\n",
    "result = itertools.starmap(operator.mul, tups)\n",
    "tuple(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for num in itertools.islice(itertools.starmap(pow, zip(fibonacci(), itertools.repeat(2))), 10):\n",
    "    print(num)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## itertools.groupby(iterable, key=None)\n",
    "### Make an iterator that returns consecutive keys and groups from the iterable. The key is a function computing a key value for each element."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for k,i in itertools.islice(itertools.groupby(fibonacci(), lambda x: 'odd' if x % 2 else 'even'), 20):\n",
    "    print(k,i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "d = defaultdict(list)\n",
    "for k,i in itertools.islice(itertools.groupby(fibonacci(), lambda x: 'odd' if x % 2 else 'even'), 20):\n",
    "    for v in i:\n",
    "        d[k].append(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## itertools.dropwhile(predicate, iterable)\n",
    "### Make an iterator that drops elements from the iterable as long as the predicate is true; afterwards, returns every element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for num in itertools.dropwhile(lambda x: x < 100, fibonacci()):\n",
    "    print(num)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## itertools.chain(*iterables)\n",
    "### Make an iterator that returns elements from the first iterable until it is exhausted, then proceeds to the next iterable, until all of the iterables are exhausted. Used for treating consecutive sequences as a single sequence.\n",
    "### un-nest two tuples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "nested = ((1,2,3),(1,2,3),(1,2,3))\n",
    "nested2 = ((4,5,6),(4,5,6),(4,5,6))\n",
    "flat = itertools.chain(*nested,*nested2)\n",
    "print(tuple(flat))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## repeat(object[, times])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "words = ['foo', 'bar']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "for word in itertools.repeat(lst, 10):\n",
    "    print(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## map was formerly called imap in the itertools module \n",
    "### applies a function to all the items in an iterable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "nums = (1,2,3,4,5)\n",
    "squared = map(lambda x: x**2, nums)\n",
    "squared"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tuple(squared)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "letters = ('a','b','c','d','d')\n",
    "tuple(map(lambda x: x * 2, letters))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## filter was formerly called ifilter in the itertools module\n",
    "### filter returns True values"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "even_num % 2 == 0, False == 0, so even_num % 0 evaluates to False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "nums = (1,2,3,4,5)\n",
    "filtered = filter(lambda x: x**2 % 2, nums)\n",
    "filtered"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tuple(filtered)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%timeit list(make_generator(one_million))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## More resources"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://docs.python.org/3/library/itertools.html#module-itertools # itertools documentation  \n",
    "https://docs.python.org/3/library/operator.html#module-operator   # operator documentation  \n",
    "https://docs.python.org/3/glossary.html#term-iterator             # iterator documentation  \n",
    "https://docs.python.org/3/glossary.html#term-generator            # generator documentation  \n",
    "https://stackoverflow.com/questions/2776829/difference-between-pythons-generators-and-iterators # generators vs iterators  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "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.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}