12_alg_combinatorics.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Foundations of Computational Economics #12\n",
    "\n",
    "by Fedor Iskhakov, ANU\n",
    "\n",
    "<img src=\"_static/img/dag3logo.png\" style=\"width:256px;\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "## Enumeration of discrete compositions\n",
    "\n",
    "<img src=\"_static/img/lab.png\" style=\"width:64px;\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Generators in Python\n",
    "\n",
    "**yield** keyword is a special kind of **return** from a function\n",
    "\n",
    "- “pauses” the function execution  \n",
    "- waits fro the next iteration request from the caller  \n",
    "- saves its state for the next call  \n",
    "\n",
    "\n",
    "Use generators instead of lists when only one element of the list is needed at any time\n",
    "\n",
    "- **saves memory**: alternative is a list of objects to be generated  \n",
    "- overhead in keeping the state of the generator function  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Iterator vs Iterable vs Generator\n",
    "\n",
    "Iterator:\n",
    "\n",
    "- object that can return its members one at a time  \n",
    "- has __iter__ and __next__ methods  \n",
    "- support StopIteration error  \n",
    "- can be used in for loops  \n",
    "\n",
    "\n",
    "Iterable:\n",
    "\n",
    "- object that can be converted to an iterator with iter() function  \n",
    "- can be used in for loops directly  \n",
    "- examples: lists, tuples, strings  \n",
    "\n",
    "\n",
    "Generator:\n",
    "\n",
    "- a particular kind of iterator  \n",
    "- can be implemented as a function with yield returns  \n",
    "- or as *comprehension expression* similar to list comprehension  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Note on range()\n",
    "\n",
    "Range object is an itarable, therefore\n",
    "\n",
    "- iter() function converts it to iterator  \n",
    "- it can be used directly in for loops  \n",
    "- but it is more than a generator: can be used in many other tasks besides looping  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# simple examples of generators\n",
    "def test_generator():\n",
    "    '''Testing generator\n",
    "    '''\n",
    "    yield 1\n",
    "    yield 5\n",
    "    yield 15\n",
    "    yield 25\n",
    "\n",
    "g = test_generator()\n",
    "print('initial call returned %d' % (next(g)))\n",
    "for i in g:\n",
    "    print('loop call returned %d' % (i))\n",
    "print('loop finished gracefully')\n",
    "next(g)  # impossible to get any output once generator is done"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def test_generator_steps():\n",
    "    '''Testing generator\n",
    "    '''\n",
    "    for i in range(10):\n",
    "        print('generator at step %d'%(i))\n",
    "        yield i\n",
    "\n",
    "g = test_generator_steps()\n",
    "for i in g:\n",
    "    print('main code at step %d' % (i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Discrete compositions\n",
    "\n",
    "$$\n",
    "(p_1, p_2, \\dots, p_n) \\text{ such that } p_i \\in \\mathbb{Z}, 0 \\le p_i \\le M, \\sum_{i=1}^{n}p_i = M\n",
    "$$\n",
    "\n",
    "$ (p_1,p_2,\\dots,p_n) $ is **composition** of number $ M $ into\n",
    "$ n $ parts."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Number of compositions\n",
    "\n",
    "- composition corresponds to cutting the interval of length $ M $ into $ n $ parts  \n",
    "- but cut points can be at the same place to allow for zeros  \n",
    "- instead let interval of length $ M+n $ be cut  \n",
    "- discrete $ \\rightarrow $ have $ M+n-1 $ points for $ n-1 $ cuts  \n",
    "- no overlaps in the latter scheme  \n",
    "\n",
    "\n",
    "$$\n",
    "\\text{Number of compositions} = {M+n-1 \\choose n-1} = \\frac{(M+n-1)!}{n!(M-1)!}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "import scipy.special\n",
    "def number_compositions(n,M):\n",
    "    '''Returns the number of discrete compositions for given parameters\n",
    "    '''\n",
    "    return int(scipy.special.comb(M+n-1,n-1)) # M+n-1 choose n-1\n",
    "\n",
    "print('n=%3d, M=%3d --> NC=%d'%(2,2,number_compositions(2,2)))\n",
    "print('n=%3d, M=%3d --> NC=%d'%(2,10,number_compositions(2,10)))\n",
    "print('n=%3d, M=%3d --> NC=%d'%(2,100,number_compositions(2,100)))\n",
    "print('n=%3d, M=%3d --> NC=%d'%(5,10,number_compositions(5,10)))\n",
    "print('n=%3d, M=%3d --> NC=%d'%(5,100,number_compositions(5,100)))\n",
    "print('n=%3d, M=%3d --> NC=%d'%(10,100,number_compositions(10,100)))\n",
    "print('n=%3d, M=%3d --> NC=%d'%(50,100,number_compositions(50,100)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Lexicographical order\n",
    "\n",
    "Composition $ p = (p_1, p_2, \\dots, p_n) $ is greater than\n",
    "composition $ p' = (p'_1, p'_2, \\dots, p'_n) $ in lexicographical sense\n",
    "iff for some $ J \\in \\{1,\\dots,n\\} $ $ p_j=p'_j $ for all $ j<J $\n",
    "and $ p_J>p'_J $.\n",
    "\n",
    "$ j=n $ is the *lowest digit*, $ j=1 $ is the *highest digit*\n",
    "\n",
    "Composition $ p $ is greater that $ p' $ iff the *highest different digit*\n",
    "of $ p $ is greater than that of $ p' $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Examples of lexicographical order\n",
    "\n",
    "- numbers in any base system  \n",
    "- words in a dictionary  \n",
    "- compositions to be generated  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def compositions(N,m):\n",
    "    '''Iterable on compositions of N with m parts\n",
    "    Returns the generator (to be used in for loops)\n",
    "    '''\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "n, M = 4, 8\n",
    "for i,k in enumerate(compositions(M,n)):\n",
    "    print('%3d'%i,end=\": \")\n",
    "    print(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hide-output": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def compositions(N,m):\n",
    "    '''Iterable on compositions of N with m parts\n",
    "    Returns the generator (to be used in for loops)\n",
    "    '''\n",
    "    cmp=[0,]*m\n",
    "    cmp[m-1]=N  # initial composition is all to the last\n",
    "    yield cmp\n",
    "    while cmp[0]!=N:\n",
    "        i=m-1\n",
    "        while cmp[i]==0: i-=1  # find lowest non-zero digit\n",
    "        cmp[i-1] = cmp[i-1]+1  # increment next digit\n",
    "        cmp[m-1] = cmp[i]-1    # the rest to the lowest\n",
    "        if i!=m-1: cmp[i] = 0  # maintain cost sum\n",
    "        yield cmp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Further learning resources\n",
    "\n",
    "- Generators vs. lists in Python\n",
    "  [https://www.youtube.com/watch?v=bD05uGo_sVI](https://www.youtube.com/watch?v=bD05uGo_sVI)  \n",
    "- Iterators and generators in Trey Hunner blog\n",
    "  [https://treyhunner.com/2018/06/how-to-make-an-iterator-in-python/](https://treyhunner.com/2018/06/how-to-make-an-iterator-in-python/)  \n",
    "- Some examples of combinatorial optimization\n",
    "  [https://neos-guide.org/content/combinatorial-optimization](https://neos-guide.org/content/combinatorial-optimization)  "
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "date": 1597824775.1801238,
  "filename": "12_alg_combinatorics.rst",
  "kernelspec": {
   "display_name": "Python",
   "language": "python3",
   "name": "python3"
  },
  "title": "Foundations of Computational Economics #12"
 },
 "nbformat": 4,
 "nbformat_minor": 4
}