tutorials/graycodes.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div align=\"right\">Massimo Nocentini\n",
    "<br>June 20, 2016: Gray codes for combinations\n",
    "<br>June 13, 2016: direct and loopless BRGC\n",
    "<br>June 7, 2016: theoretical intro\n",
    "<br>May 19, 2016: BRGC\n",
    "</div>\n",
    "\n",
    "<div align=\"center\">\n",
    "<b>Abstract</b><br>\n",
    "This document collect some theory and arguments about <i>Gray codes</i>.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%run ../python-libs/inpututils.py\n",
    "%run ../python-libs/graycodes.py\n",
    "%run ../python-libs/bits.py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Combinatorial Generation\n",
    "\n",
    "The theory described here is given by [Frank Ruskey][fr] and adapted from his [Combinatorial Generation][cg] book. We use the following arguments to implement some Python functions, available [here][libs:gray]. In this introduction we report some concepts and definitions from Ruskey that we believe interesting and necessary for what follows, starting with the meaning of *Combinatorial Generation*:\n",
    "\n",
    ">*Let's look at all the possibilities.* This phrase sums up the outlook of this book. In\n",
    "computer science, mathematics, and in other fields it is often necessary to examine all of\n",
    "a finite number of possibilities in order to solve a problem or gain insight into the solution\n",
    "of a problem. These possibilities often have an underlying combinatorial structure which\n",
    "can be exploited in order to obtain an efficient algorithm for generating some appropriate\n",
    "representation of them.\n",
    "\n",
    "About *complexity*:\n",
    "\n",
    ">Not much attention has been paid to the model of computation in the area of combinatorial\n",
    "generation. For the most part authors use the random access machine model. This is more\n",
    "or less like counting operations in a Pascal program, with the understanding that integers\n",
    "can be arbitrarily large and the assumption that standard arithmetic operations can be\n",
    "done in constant time. For large integers this is an unrealistic assumption. It is generally\n",
    "the case that integers are small in generation algorithms, but that they are large in ranking\n",
    "and unranking algorithms. We will therefore measure ranking and unranking algorithms in\n",
    "terms of the number of arithmetic operations used.\n",
    "\n",
    "About *analysis*:\n",
    "\n",
    ">There are two terms that are used throughout the book. We strive to develop algorithms\n",
    "that have these properties. \n",
    "   - **CAT** algorithms: the holy grail of generating combinatorial objects is to find an algorithm\n",
    "   that runs in Constant Amortized Time. This means that the amount of computation, after\n",
    "   a small amount of preprocessing, is proportional to the number of objects that are listed.\n",
    "   *We do not count the time to actually output or process the objects; we are only concerned\n",
    "   with the amount of data structure change that occurs as the objects are being generated*. \n",
    "   Suppose that the input to our generation algorithm is $n$, and that this will produce $N$\n",
    "   objects, each of \"size\" $n$. A CAT algorithm has running time $\\mathcal{O}(N)$. In the typical \n",
    "   application of combinatorial generation, each object, as it is produced, is processed somehow.\n",
    "   If this processing takes time $\\mathcal{O}(n)$, then having a CAT algorithm has no advantage over\n",
    "   having one with running time $\\mathcal{O}(nN)$, since the total running time is $\\mathcal{O}(nN)$ \n",
    "   in either case.\n",
    "   - **BEST** algorithms: this means *Backtracking Ensuring Success at Terminals*. In other\n",
    "   words, the algorithm is of the backtracking type, but every leaf of the backtracking tree is\n",
    "   an object of the desired type; it is a *success*.\n",
    "\n",
    "*Don't count the output* principle:\n",
    "\n",
    ">There are are many papers about generating combinatorial objects that describe an\n",
    "$\\mathcal{O}(nN)$ running time as *optimal*, because this is the amount of output produced by the\n",
    "algorithm — each object has size $n$ and there are $N$ objects in total. This is a misguided\n",
    "notion that has its roots in the way lower bounds are discussed in the traditional introduction\n",
    "to complexity theory course. There the *trivial lower bound* says that the amount of output\n",
    "gives a lower bound on the amount of computation — of course it says the same thing in\n",
    "our setting, *but the amount of output is the wrong thing to measure*.\n",
    ">>**Don't Count the Output Principle**: In combinatorial generation it is the\n",
    "amount of data structure change that should be measured in determining the complexity \n",
    "of an algorithm; the time required to output (and process) each object should be ignored.\n",
    "\n",
    ">The *trivial lower bound* for combinatorial generation is $\\mathcal{Θ}(N )$; it is independent of $n$.\n",
    "Now back to our typical application,\n",
    "where processing each object took time $\\mathcal{O}(n)$ even though our generation algorithm was\n",
    "CAT. Wouldn't it be nice if the $\\mathcal{O}(nN)$ could be brought down to $\\mathcal{O}(N)$? \n",
    "This is frequently possible! If you go back and observe how successive objects are processed, *it is often the\n",
    "case that the amount of processing required is proportional to the amount of change that\n",
    "successive objects undergo.*\n",
    "\n",
    "A last concept, *ordering*:\n",
    "\n",
    ">*Lexicographic* order is based on the familiar idea as the ordering of words in dictionaries.\n",
    "The only requirement is that *the letters that make up the alphabet of the language be\n",
    "ordered*. In the definitions below we use $\\prec$ to denote the assumed underlying ordering of\n",
    "the symbols of the alphabet and $<$ to denote orderings of strings (and, of course, integers). \n",
    "We remark again that in most instances the alphabet is the set of natural numbers under the usual numeric ordering\n",
    "$0 \\prec 1 \\prec 2 \\prec \\ldots$.\n",
    "\n",
    "We report definitions of three orderings:\n",
    "\n",
    "   - *lexicographic* (or *lex*) order, denoted by $<_{l}$: \n",
    "   $a_1 a_2 \\ldots a_n <_l b_1 b_2 \\ldots b_m$ if either\n",
    "      1. for some $k$, $a_k \\prec b_k$ and $a_i = b_i$ for $i\\in\\lbrace 1, 2, \\ldots , k − 1\\rbrace$, or\n",
    "      2. $n < m$ and $a_i = b_i$ for $i \\in\\lbrace 1, 2, \\ldots , n\\rbrace$.\n",
    "   - *reverse lexicographic* (or *relex*) order, denoted by $<_{r}$: $a_1 a_2 \\ldots a_n <_r b_1 b_2 \\ldots b_m$\n",
    "   if $b_1 b_2 \\ldots b_m <_l a_1 a_2 \\ldots a_n$ in lex order.\n",
    "   - *co-lexicographic* (or *colex*) order, denoted by $<_{c}$: $a_1 a_2 \\ldots a_n <_c b_1 b_2 \\ldots b_m$\n",
    "   if $a_n \\ldots a_2 a_1 <_l b_m \\ldots b_2 b_1$ in lex order.\n",
    "\n",
    "[fr]:http://webhome.cs.uvic.ca/~ruskey/\n",
    "[cg]:http://www.1stworks.com/ref/RuskeyCombGen.pdf\n",
    "[libs:gray]:https://github.com/massimo-nocentini/competitive-programming/blob/master/python-libs/graycodes.py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binary Reflected Gray Codes\n",
    "\n",
    "Here we introduce combinatorial Gray codes, which are lists of combinatorial\n",
    "objects such that are pairwise *close*. Quoting Ruskey:\n",
    "\n",
    ">Suppose that we wish to list all $2^n$ bitstrings of length $n$, in such a way that each bitstring\n",
    "differs from its predecessor by a single bit. Such lists are called *binary Gray codes*, named\n",
    "after Frank Gray who used them in a patent he obtained for \"pulse code communication\".\n",
    "\n",
    "Using *reflection*, it yields a recursive definition:\n",
    "\n",
    ">There is a very simple recursive algorithm for generating one particular Gray code, known\n",
    "as the *binary reflected Gray code (BRGC)*.\n",
    "The binary reflected Gray code on *n* elements, $\\textbf{G}_n$, is defined recursively by letting\n",
    "$\\textbf{G}_0$ be the single element sequence containing the empty string $\\epsilon$, \n",
    "and letting $\\textbf{G}_n$ be the list obtained by prefixing each element of $\\textbf{G}_{n−1}$ \n",
    "with a 0 and then prefixing each element of $\\textbf{G}_{n−1}$ *in reversed order* with a 1. For example: \n",
    "$\\textbf{G}_1 = (0,1), \\textbf{G}_2 = (00, 01, 11, 10), \\textbf{G}_3 = (000, 001, 011, 010, 110, 111, 101, 100)$.\n",
    "The $n$-dimensional hypercube, or $n$-cube, $Q_n$ , may be considered as the graph whose\n",
    "vertices consist of all bitstrings of length $n$ and where two vertices are joined by an edge\n",
    "if they differ by a single bit. The problem of finding a Gray code corresponds to finding a\n",
    "Hamilton path in $Q_n$: observe that the binary reflected Gray\n",
    "code actually defines a Hamiltonian cycle on the $n$-cube since the first and last bitstrings\n",
    "only differ by a single bit.\n",
    "\n",
    "There is an interesting connection between the Towers of Hanoi problem, the binary\n",
    "reflected Gray code, and ordinary counting in binary:\n",
    "\n",
    ">Now suppose that the disks are numbered $0, 1, \\ldots , n-1$ where 0 is the smallest disk and\n",
    "$n-1$ is the largest disk. Let $T_n$ denote the sequence of disks that are moved in solving the\n",
    "$n$ disk Towers of Hanoi problem. Looking at the following table, $T_3 = 0, 1, 0, 2, 0, 1, 0$. \n",
    "It turns out that the number at position k in T_n, zero-based, \n",
    "is the index of the bit that changes in the bitstring of $\\textbf{G}_n$ in position $k$, \n",
    "and that this is equal to the position $k$ \n",
    "of the rightmost 0, counting from the right, in the bitstring when counting in binary.\n",
    "The sequence $T_n$ is called the transition sequence of the BRGC. Every Hamilton path on\n",
    "the $n$-cube has a transition sequence and these paths are often specified by their transition\n",
    "sequences.\n",
    "$$\n",
    "\\begin{array}{ccc}\n",
    "\\text{binary} & \\text{Gray code} & T_n\\\\\n",
    "\\hline\n",
    "000 & 000 & 0 \\\\\n",
    "001 & 001 & 1 \\\\\n",
    "010 & 011 & 0 \\\\\n",
    "011 & 010 & 2 \\\\\n",
    "100 & 110 & 0 \\\\\n",
    "101 & 111 & 1 \\\\\n",
    "110 & 101 & 0 \\\\\n",
    "111 & 100 &  \\\\\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "We will first derive two functions, for *ranking* and *unranking* gray codes and, lately, a function to efficiently compute the position of the rightmost 0 when counting in binary."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## *Unranking* Gray codes\n",
    "\n",
    "As a notational convenience we will now assume that the Gray code\n",
    "bitstrings are indexed $g_{n} \\ldots g_1$, in contrast to the usual 0-based indexing.\n",
    "\n",
    "Let $r$, standing for *rank*, be a function defined inductively as follows:\n",
    "$$\n",
    "    r()=0 \\\\\n",
    "    r(0 g_{n-1} \\ldots g_{1} ) = r(g_{n-1} \\ldots g_{1} ) \\\\\n",
    "    r(1 g_{n-1} \\ldots g_{1} ) = 2^{n-1} + \\bar{r}(g_{n-1} \\ldots g_{1} )\n",
    "$$\n",
    "where auxiliary function $\\bar{r}$ is defined as:\n",
    "$$\n",
    "    \\bar{r}()=0 \\\\\n",
    "    \\bar{r}(0 g_{n-1} \\ldots g_{1} ) = 2^{n-1} + \\bar{r}(g_{n-1} \\ldots g_{1} )  \\\\\n",
    "    \\bar{r}(1 g_{n-1} \\ldots g_{1} ) = r(g_{n-1} \\ldots g_{1} )\n",
    "$$\n",
    "\n",
    "In Ruskey words, slightly modified:\n",
    "\n",
    ">Let $\\textbf{g}=g_{n}\\ldots g_{1}$ be a Gray code and assume $r(g_{n}\\ldots g_{1})=(b_{n-1}\\ldots b_{0})_{2}$. This mutual recursive definition may be interpreted as setting $b_{n−1}$ to 0 or 1, depending upon whether\n",
    "the term $2^{n−1}$ in the binary expansion is present or not. The repeated application of these\n",
    "recurrence relations to a bitstring may then be thought of as sweeping functions $r$ or $\\bar{r}$ from left-to-right as illustrated in the example below, where $\\textbf{g}=g_{n}\\ldots g_{1} = 111010101$:\n",
    "\n",
    "$$\n",
    "\\begin{array}{cccccccccc}\n",
    "       & g_{9} & g_{8} & g_{7} & g_{6} & g_{5} & g_{4} & g_{3} & g_{2} & g_{1} \\\\\n",
    "     r & 1 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\\\\n",
    "     1 & \\bar{r} & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\\\\n",
    "     1 & 0 & r & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\\\\n",
    "     1 & 0 & 1 & \\bar{r} & 0 & 1 & 0 & 1 & 0 & 1 \\\\\n",
    "     1 & 0 & 1 & 1 & \\bar{r} & 1 & 0 & 1 & 0 & 1 \\\\\n",
    "     1 & 0 & 1 & 1 & 0 & r & 0 & 1 & 0 & 1 \\\\\n",
    "     1 & 0 & 1 & 1 & 0 & 0 & r & 1 & 0 & 1 \\\\\n",
    "     1 & 0 & 1 & 1 & 0 & 0 & 1 & \\bar{r} & 0 & 1 \\\\\n",
    "     1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & \\bar{r} & 1 \\\\\n",
    "     1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & r \\\\\n",
    "     b_{8} & b_{7} & b_{6} & b_{5} & b_{4} & b_{3} & b_{2} & b_{1} & b_{0} \\\\\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    ">With $g_{n+1}$ = 0, note that an $r$ always has a 0 to its left and a $\\bar{r}$ has a 1 to its left. Thus\n",
    "for each sub-sequence $b_{i}\\,\\sigma\\,g_{i}$, where $\\sigma\\in\\lbrace r, \\bar{r}\\rbrace$, there are *four* possibilities $\\lbrace 0\\,r\\,0, 0\\,r\\,1, 1\\,\\bar{r}\\,0, 1\\,\\bar{r}\\,1\\rbrace$. The resulting values of $b_{i−1}$ are $\\lbrace 0, 1, 1, 0 \\rbrace$ in those four cases, respectively:\n",
    "\n",
    "$$\n",
    "\\begin{array}{ccc}\n",
    "    b_{i} & \\sigma & g_{\\hat{i}} \\\\\n",
    "     & \\downarrow & \\\\\n",
    "    b_{i} & b_{i-1} & \\sigma' \\\\\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    ">where $\\downarrow$ is the application of function $\\sigma \\in \\lbrace r, \\bar{r}\\rbrace$, which sets $b_{i-1}$ and function $\\sigma'$ according to the mutual definition. From this we observe that $b_{i−1} = b_i \\oplus g_{\\hat{i}}$ , where $\\oplus$ denotes exclusive-or: the bit below an $r$ or $\\bar{r}$ is the exclusive-or of the bits left and right of the $r$ or $\\bar{r}$. Therefore the following holds:\n",
    "\n",
    "$$ r(g_{n}\\ldots g_{1})=(b_{n-1}\\ldots b_{0})_{2} \\rightarrow b_{i−1} = b_i \\oplus g_{\\hat{i}} $$\n",
    "\n",
    ">where $g_{\\hat{i}} = g_{i-1}$.\n",
    " \n",
    "We can use the above argument to produce the Gray code with generic symbol $g_{i-1}$, zero-based indexing, in rank or position $k$ (named $b$ above) using the relation $k_i \\oplus k_{i−1} =  g_{i-1}$ and visualized as:\n",
    "\n",
    "$$\n",
    "\\begin{array}{ccccc}\n",
    "    b_{i} & & b_{i-1} & & b_{i-2} \\\\\n",
    "    \\oplus & \\searrow & \\oplus & \\searrow & \\oplus \\\\\n",
    "    b_{i+1} & & b_{i} & & b_{i-1} \\\\\n",
    "    = & & = & & = \\\\\n",
    "    g_{i} & & g_{i-1} & & g_{i-2} \\\\\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "observe that the former and latter rows stay steal, only the middle is shifted to the right."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Indirect generation\n",
    "\n",
    "Python function `graycode_unrank` that implements arguments above is pretty elegant; however, this generation is *indirect* since it does not provide the *position* of the changing bit among adjacent codes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "```python\n",
       "def graycode_unrank(k): \n",
       "    \"\"\"\n",
       "    Return the *graycode* in position `k` respect binary reflected construction.\n",
       "    \n",
       "    Of course, argument `k` should be a *non-negative* integer.\n",
       "\n",
       "    Examples\n",
       "    ========\n",
       "\n",
       "    >>> bin(graycode_unrank(0b101100110))\n",
       "    '0b111010101'\n",
       "\n",
       "    \"\"\"\n",
       "    g = k ^ (k >> 1)\n",
       "    return g\n",
       "\n",
       "```"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "python_code(graycode_unrank)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following is an iterable of Gray codes we saw in the example above, namely all of them of length 3, pretty-printed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0b000\n",
      "0b001\n",
      "0b011\n",
      "0b010\n",
      "0b110\n",
      "0b111\n",
      "0b101\n",
      "0b100\n"
     ]
    }
   ],
   "source": [
    "print('\\n'.join(list(binary_reflected_graycodes(3, justified=True))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Moreover, we have implemented an *operator* which allows us to process an iterable of codes pairwise, possibly plugging-in custom behavior via `lambda` expressions. Previous table with the position of the changing-bit can be rebuilt as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  0b0\t  0b0\t0\n",
      "  0b1\t  0b1\t1\n",
      " 0b10\t 0b11\t0\n",
      " 0b11\t 0b10\t2\n",
      "0b100\t0b110\t0\n",
      "0b101\t0b111\t1\n",
      "0b110\t0b101\t0\n",
      "0b111\t0b100\t2\n"
     ]
    }
   ],
   "source": [
    "from itertools import count\n",
    "\n",
    "example_graycodes = binary_reflected_graycodes(length=3)\n",
    "for c, (o, s, p, r) in zip(count(), binary_reflected_graycodes_reduce(example_graycodes)):\n",
    "    print('{:>5}\\t{:>5}\\t{}'.format(bin(c), bin(o), p))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Direct generation\n",
    "\n",
    "It is possible to write a function `graycodes_direct` which provides codes and changing-bit positions in parallel, here is the code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "```python\n",
       "def graycodes_direct(n):\n",
       "    \"\"\"\n",
       "    Returns an iterable of Gray codes of length `n`, each paired with changing-bit positions.\n",
       "\n",
       "    \"\"\"\n",
       "    code = 0\n",
       "\n",
       "    def swap(i):\n",
       "        nonlocal code\n",
       "        code = toggle_bits(code, i)\n",
       "        yield code, i\n",
       "\n",
       "    def gen(i):\n",
       "        if i > -1:\n",
       "            yield from itertools.chain(gen(i-1), swap(i), gen(i-1))\n",
       "\n",
       "    yield code, -1\n",
       "    yield from gen(n-1)\n",
       "\n",
       "```"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "python_code(graycodes_direct)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and can be used to build the same example table; observe that the changing-bit positions sequence is shifted *forward* by one:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  0b0\t  0b0\t-1\n",
      "  0b1\t  0b1\t0\n",
      " 0b10\t 0b11\t1\n",
      " 0b11\t 0b10\t0\n",
      "0b100\t0b110\t2\n",
      "0b101\t0b111\t0\n",
      "0b110\t0b101\t1\n",
      "0b111\t0b100\t0\n"
     ]
    }
   ],
   "source": [
    "for i, (code, changingbit_position) in zip(count(), graycodes_direct(3)):\n",
    "    print('{:>5}\\t{:>5}\\t{}'.format(bin(i),bin(code), changingbit_position))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Counting without cycles\n",
    "\n",
    "In this section we fullfil the last correspondence among binary counting and graycodes generation. Here we will develop a *loopless* algorithm such that, keeping track of the rightmost 0 (in the least significant part), allows to build graycodes: such tracking avoid scans to find it and break the worst cases in which that 0-bit is in the most significant part of the number. Begin defining an array $\\tau$ which is a representation of the counting number $b_{n-1}b_{n-2}\\ldots b_{1}b_{0}$, aiming to catch *0-bits positions*, defined as follows:\n",
    "\n",
    "$$\n",
    "\\tau_{i} = \\left\\lbrace \n",
    "\\begin{array}{ll}\n",
    "i & \\text{if } b_{i}=0 \\vee b_{i-1}=1\\\\\n",
    "\\min_{k\\in\\lbrace i+1,\\ldots,n\\rbrace}{\\lbrace k: b_{k}=0 \\rbrace} & \\text{if } b_{i}=1 \\vee b_{i-1}=0\n",
    "\\end{array} \n",
    "\\right.\n",
    "$$\n",
    "\n",
    "In words, if $b_{i}$ is 0-bit than $\\tau_{i}$ is its own position $i$, otherwise if the previous bit $b_{i-1}$ is 1-bit too, then set $\\tau_{i}=i$ again because they are in a sequence of 1 in a row. On the other hand, if bit $b_{i}$ is the last 1-bit in a sequence of ones, so $b_{i-1}=0$, then find the closer position in $\\tau$ which is zero. Follows four examples with $n-1=10$:\n",
    "\n",
    "$$\n",
    "\\begin{array}{ccccccccccc||ccccccccccc}\n",
    "b_{10} & b_9 & b_8 & b_7 & b_6 & b_5 & b_4 & b_3 & b_2 & b_1 & b_0 & \n",
    "\\tau_{10} & \\tau_9 & \\tau_8 & \\tau_7 & \\tau_6 & \\tau_5 & \\tau_4 & \\tau_3 & \\tau_2 & \\tau_1 & \\tau_0 \\\\\n",
    "\\hline\n",
    "1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 &   \n",
    "    10 & \\textbf{11} & 8 & \\textbf{8} & 6 & 5 & 4 & 3 & 2 & 1 & \\textbf{4} \\\\\n",
    "1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 &   \n",
    "    10 & \\textbf{11} & 8 & \\textbf{8} & 6 & 5 & \\textbf{5} & 3 & 2 & 1 & 0 \\\\\n",
    "1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 &   \n",
    "    10 & \\textbf{11} & 8 & \\textbf{8} & 6 & 5 & \\textbf{5} & 3 & 2 & 1 & \\textbf{1} \\\\\n",
    "1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 &   \n",
    "    10 & \\textbf{11} & 8 & \\textbf{8} & 6 & 5 & \\textbf{5} & 3 & 2 & \\textbf{2} & 0 \\\\\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "where in __boldface__ are value in $\\tau$ set by the *second* clause in the definition; therefore, the changing-bit in the graycode, lying *on the same row in the table* together with the binary counter, has position $\\tau_{0}$, since it is the minimum position where a 0-bit appears in the counter.\n",
    "\n",
    "In order to derive an efficient function using $\\tau$ array, we study 4 cases, namely the four combinations of $b_{i+1}$ and $b_{0}$ binary values, where $\\tau_{0}=i$:\n",
    "\n",
    "   - $b_{i+1}=0 \\wedge b_{0}=1$:\n",
    "   $$\n",
    "\\begin{array}{cccccc|cccccc}\n",
    "b_{i+1} & b_{i} & b_{i-1} & \\ldots & b_1 & b_0 & \n",
    "\\tau_{i+1} & \\tau_i & \\tau_{i-1} & \\ldots & \\tau_1 & \\tau_0 \\\\\n",
    "\\hline\n",
    "0 & 0 & 1 & ones & 1 & 1 &   i+1 & i & i-1 & \\ldots & 1 & i \\\\\n",
    "0 & 1 & 0 & zeroes & 0 & 0 &   i+1 & i+1 & i-1 & \\ldots & 1 & 0 \\\\\n",
    "\\end{array}   \n",
    "   $$\n",
    "   hence the following updates take place: $\\tau_{0}\\leftarrow 0$, $\\tau_{i}\\leftarrow i+1 = \\tau_{i+1}$ and $\\tau_{i+1}\\leftarrow i+1$;\n",
    "   \n",
    "   - $b_{i+1}=1 \\wedge b_{0}=1$:\n",
    "   $$\n",
    "\\begin{array}{cccccc|cccccc}\n",
    "b_{i+1} & b_{i} & b_{i-1} & \\ldots & b_1 & b_0 & \n",
    "\\tau_{i+1} & \\tau_i & \\tau_{i-1} & \\ldots & \\tau_1 & \\tau_0 \\\\\n",
    "\\hline\n",
    "1 & 0 & 1 & ones & 1 & 1 &   j & i & i-1 & \\ldots & 1 & i \\\\\n",
    "1 & 1 & 0 & zeroes & 0 & 0 &   i+1 & j & i-1 & \\ldots & 1 & 0 \\\\\n",
    "\\end{array}   \n",
    "   $$\n",
    "   where $j = min_{k\\in\\lbrace i+2,\\ldots, n\\rbrace}{\\lbrace k: b_{k}=0\\rbrace}$; hence the following updates take place: $\\tau_{0}\\leftarrow 0$, $\\tau_{i}\\leftarrow j = \\tau_{i+1}$ and $\\tau_{i+1}\\leftarrow i+1$;\n",
    "   \n",
    "   - $b_{0}=0 \\wedge b_{1}=0$, so $\\tau_{0}=i=0$, hence $b_{i+1}=b_{1}$:\n",
    "   $$\n",
    "\\begin{array}{cc|cc}\n",
    " b_{i+1} = b_1 & b_{i} = b_0 & \\tau_{i+1} = \\tau_1 & \\tau_{i}=\\tau_0 \\\\\n",
    "\\hline\n",
    " 0 & 0 &   1 & 0 \\\\\n",
    " 0 & 1 &   1 & 1 \\\\\n",
    "\\end{array}   \n",
    "   $$\n",
    "   hence the following updates take place: $\\tau_{0}\\leftarrow 0$ (implicitly), $\\tau_{i}\\leftarrow 1 = \\tau_{i+1}$ and $\\tau_{i+1}\\leftarrow 1 = i+1$;\n",
    "   \n",
    "   - $b_{0}=0 \\wedge b_{1}=1$, so $\\tau_{0}=i=1$, hence $b_{i+1}=b_{1}$:\n",
    "   $$\n",
    "\\begin{array}{cc|cc}\n",
    " b_{i+1} = b_1 & b_{i} = b_0 & \\tau_{i+1} = \\tau_1 & \\tau_{i}=\\tau_0 \\\\\n",
    "\\hline\n",
    " 1 & 0 &   2 & 0 \\\\\n",
    " 1 & 1 &   1 & 2 \\\\\n",
    "\\end{array}   \n",
    "   $$\n",
    "   hence the following updates take place: $\\tau_{0}\\leftarrow 0$ (implicitly), $\\tau_{i}\\leftarrow 2 = \\tau_{i+1}$ and $\\tau_{i+1}\\leftarrow 1 = i+1$.\n",
    "   \n",
    "So in every case, the following assignments occur *sequentially*:\n",
    "$$\n",
    "\\tau_{0}\\leftarrow 0 \\\\\n",
    "\\tau_{i}\\leftarrow \\tau_{i+1} \\\\\n",
    "\\tau_{i+1}\\leftarrow i+1 \\\\\n",
    "$$\n",
    "\n",
    "Previous argument yield the following functions quite naturally:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "```python\n",
       "def rightmost_zeroes_in_binary_counting(n):\n",
       "    \"\"\"\n",
       "    I'm a generator of positions of *rightmost zeroes* in binary counting up to `2**n -1`.\n",
       "\n",
       "    This implements the loopless algorithm designed by Frank Ruskey; it is more\n",
       "    efficient than natural counting and scanning for rightmost zeroes, which is CAT however.\n",
       "\n",
       "    Examples\n",
       "    ========\n",
       "\n",
       "    Generate the transition sequence to solve the Hanoi tower problem with 3 disks:\n",
       "    >>> list(rightmost_zeroes_in_binary_counting(3))\n",
       "    [0, 1, 0, 2, 0, 1, 0]\n",
       "    \n",
       "    according to the result, we have to move first disk 0, then disk 1, then disk 0 again,\n",
       "    then disk 2, next disk 0, next disk 1 and, finally, disk 0; obviously, recipient peg\n",
       "    is according to the rule of the game.\n",
       "\n",
       "    \"\"\"\n",
       "    tau = list(range(n+1))\n",
       "\n",
       "    while tau[0] != n:\n",
       "        yield tau[0]\n",
       "        i = tau[0]\n",
       "        tau[0], tau[i], tau[i+1] = 0, tau[i+1], i+1\n",
       "\n",
       "def graycodes_by_transition_sequence(positions):\n",
       "    \"\"\"\n",
       "    I'm a generator of graycodes, flipping bits according to transitions sequence `positions`.\n",
       "\n",
       "    \"\"\"\n",
       "\n",
       "    graycode = 0\n",
       "\n",
       "    yield graycode, -1\n",
       "\n",
       "    for p in positions:\n",
       "        graycode = toggle_bits(graycode, p)\n",
       "        yield graycode, p\n",
       "\n",
       "```"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "python_code(rightmost_zeroes_in_binary_counting, graycodes_by_transition_sequence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 0, 2, 0, 1, 0]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(rightmost_zeroes_in_binary_counting(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  0b0\t  0b0\t-1\n",
      "  0b1\t  0b1\t0\n",
      " 0b10\t 0b11\t1\n",
      " 0b11\t 0b10\t0\n",
      "0b100\t0b110\t2\n",
      "0b101\t0b111\t0\n",
      "0b110\t0b101\t1\n",
      "0b111\t0b100\t0\n"
     ]
    }
   ],
   "source": [
    "graycodes_with_positions = graycodes_by_transition_sequence(rightmost_zeroes_in_binary_counting(3))\n",
    "for b, (code, p) in zip(count(), graycodes_with_positions):\n",
    "    print('{:>5}\\t{:>5}\\t{}'.format(bin(b), bin(code), p))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Simply via bitmasking\n",
    "Previous argument is pretty creative but a bit hard to digest. Moreover, there is a *bitmasking* technique that allows us to find the position of the rightmost 0-bit. Here's the code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "```python\n",
       "def turn_on_last_zero(S): \n",
       "    \"\"\"\n",
       "    Turns on the rightmost 0-bit in word `S`, producing all 1's if none.\n",
       "\n",
       "    By product, the position of toggled 0-bit is returned.\n",
       "\n",
       "    Examples\n",
       "    ========\n",
       "\n",
       "    When a 0-bit is present:\n",
       "    >>> S, z = turn_on_last_zero(0b10100111)\n",
       "    >>> bin(S)\n",
       "    '0b10101111'\n",
       "    >>> z\n",
       "    3\n",
       "\n",
       "    When a 0-bit is *implicitly* present:\n",
       "    >>> S, z = turn_on_last_zero(0b11111)\n",
       "    >>> bin(S)\n",
       "    '0b111111'\n",
       "    >>> z\n",
       "    5\n",
       "    \"\"\"\n",
       "    SS = S | (S + 1)\n",
       "    z = (SS ^ S).bit_length()-1\n",
       "    return SS, z\n",
       "\n",
       "```"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "python_code(turn_on_last_zero)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and can be used directly with binary counting:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 0\n",
      "3 1\n",
      "3 0\n",
      "7 2\n",
      "5 0\n",
      "7 1\n",
      "7 0\n"
     ]
    }
   ],
   "source": [
    "for i in range(2**3-1):\n",
    "    I, z = turn_on_last_zero(i)\n",
    "    print(I, z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## *Ranking* Gray codes\n",
    "\n",
    "Although not required, we can work the relation $k_{i−1} = k_i \\oplus  g_{i-1}$ backwards, namely given a Gray code `g` find the corresponding position or rank `k`. To succeed, we think inductively as follows: rewrite the same schema, starting from the very left, namely the most significant part\n",
    "\n",
    "$$\n",
    "\\begin{array}{ccccc}\n",
    "    b_{n-1} & & b_{n-2} & & b_{n-3} \\\\\n",
    "    = & \\searrow & = & \\searrow & = \\\\\n",
    "    0 & & b_{n-1} & & b_{n-2} \\\\\n",
    "    \\oplus & & \\oplus & & \\oplus \\\\\n",
    "    g_{n-1} & & g_{n-2} & & g_{n-3} \\\\\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "where the row in the middle starts with 0 because it is shifted to the right by one. Doing the leftmost $\\oplus$ and copying it according to the arrow -- after all, the middle row *is* the first one, just shifted -- we get:\n",
    "\n",
    "$$\n",
    "\\begin{array}{ccccc}\n",
    "    g_{n-1} & & b_{n-2} & & b_{n-3} \\\\\n",
    "    = & \\searrow & = & \\searrow & = \\\\\n",
    "    0 & & g_{n-1} & & b_{n-2} \\\\\n",
    "    \\oplus & & \\oplus & & \\oplus \\\\\n",
    "    g_{n-1} & & g_{n-2} & & g_{n-3} \\\\\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "We can complete the induction steps, obtaining:\n",
    "\n",
    "$$\n",
    "\\begin{array}{ccccc}\n",
    "    g_{n-1} & & g_{n-2}\\oplus g_{n-1} & & g_{n-3}\\oplus g_{n-2}\\oplus g_{n-1} \\\\\n",
    "    = & \\searrow & = & \\searrow & = \\\\\n",
    "    0 & & g_{n-1} & & g_{n-2}\\oplus g_{n-1} \\\\\n",
    "    \\oplus & & \\oplus & & \\oplus \\\\\n",
    "    g_{n-1} & & g_{n-2} & & g_{n-3} \\\\\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "it seems that we have to *cumulate* the given gray code. In order to derive working Python code, we can split the above schema according the following equivalent one:\n",
    "\n",
    "$$\n",
    "\\begin{array}{ccc}\n",
    "    b_{n-1} & b_{n-2} & b_{n-3} \\\\\n",
    "    = & = & = \\\\\n",
    "    g_{n-1} & g_{n-1} & g_{n-1} \\\\\n",
    "     & \\oplus & \\oplus \\\\\n",
    "      & g_{n-2} & g_{n-2} \\\\\n",
    "     &  & \\oplus \\\\\n",
    "      &  & g_{n-3} \\\\\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "\n",
    "This argument is implemented in function `gray_position`, where we code the repetition of each symbol $g_{i}$ building a sequence of ones of the correct length at each iteration, multiplied by a check that ensure that such symbol is actually 1:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "```python\n",
       "def graycode_rank(g):\n",
       "    \"\"\"\n",
       "    Returns the *position* (namely *ranking*) of graycode `g` respect binary reflected construction.\n",
       "\n",
       "    Examples\n",
       "    ========\n",
       "\n",
       "    >>> bin(graycode_rank(0b111010101))\n",
       "    '0b101100110'\n",
       "\n",
       "    \"\"\"\n",
       "    k=0\n",
       "    for i in reversed(range(g.bit_length())):\n",
       "        k ^= set_all(i+1) * is_on(g, i)\n",
       "\n",
       "    return k\n",
       "\n",
       "```"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "python_code(graycode_rank)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "where auxiliary functions are defined as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "```python\n",
       "def is_on(S, j): \n",
       "    \"\"\"\n",
       "    Returns 1 if and only if the `j`-th item of the set `S` is on.\n",
       "\n",
       "    Examples\n",
       "    ========\n",
       "\n",
       "    Check if the 3-th and then 2-nd item of the set is on:\n",
       "    >>> S = 0b101010\n",
       "    >>> is_on(S, 3), is_on(S, 2)\n",
       "    (1, 0)\n",
       "\n",
       "    \"\"\"\n",
       "    return (S & (1 << j)) >> j\n",
       "\n",
       "def set_all(n):\n",
       "    return (1 << n) - 1\n",
       "\n",
       "```"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "python_code(is_on, set_all)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Gray codes for *combinations*\n",
    "\n",
    "Quoting the introduction from [Ruskey][cg], section 5.3, directly:\n",
    "\n",
    ">In this section we develop several Gray codes for *combinations*; that is, for $k$-subsets taken\n",
    "from the set $[n] = \\lbrace1, 2, . . . , n\\rbrace$. For the most part, we identify each subset with a bitstring\n",
    "of length $n$ with exactly $k$ ones; i.e., with an element of $\\textbf{B}(n, k)$. The\n",
    "algorithms developed can be easily modified to generate the elements of the other common\n",
    "representation, $\\textbf{A}(n, k)$ (recall that it is the set of monotonically increasing sequences\n",
    "of length $k$ with elements taken from $[n]$; see (4.2) of [Combinatorial Generation][cg]).\n",
    "There are many closeness conditions (or relations) that can be applied to bitstrings\n",
    "with a fixed number of ones. In this section we consider five natural closeness relations.\n",
    "These relations can be defined more generally on any set of strings in which the number of\n",
    "occurances of each symbol is the same in each string.\n",
    "   - the *transposition* condition: The two permutations differ in exactly *two*\n",
    "positions: call the two positions $i$ and $j$. Example: $\\underline{0}021\\underline{1}$ and $\\underline{1}021\\underline{0}$. In this example the positions that\n",
    "change are $i = 1$ and $j = 5$, and are underlined, as they will be in each of the example\n",
    "that follows.\n",
    "   - the *homogenous transposition* condition: The permutations, say $\\pi$ and\n",
    "$\\phi$ differ in exactly two positions $i$ and $j$, and only symbols less than or equal to\n",
    "$min(\\pi_i , \\phi_j)$ occur between those two positions; example: $\\underline{0}000\\underline{1}12$ and \n",
    "$\\underline{1}000\\underline{0}12$.\n",
    "\n",
    "[cg]:http://www.1stworks.com/ref/RuskeyCombGen.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Using *transposition* relation\n",
    "\n",
    "Again in Ruskey words:\n",
    "\n",
    ">Algorithms satisfying the *transposition* criteria are sometimes said to be *revolving door*\n",
    "algorithms. Imagine two rooms $A$ and $B$ connected by a revolving door that operates only\n",
    "if occupied by two persons, one from each room. As a person leaves one room, they enter\n",
    "the other, so the door acts to swap two persons. Given $k$ persons in the first room, the\n",
    "problem is to sequence through all possible combinations of persons in the first\n",
    "room so that each such combination occurs exactly once. This is precisely the same as the\n",
    "question of generating combinations by transpositions.\n",
    "The transposition closeness condition is handled in a manner similar to the way subsets\n",
    "were done. That is, we rely on the classic recurrence relation for binomial coefficients, but\n",
    "reverse the list corresponding to one of the terms.\n",
    "\n",
    "This yield to the following relation:\n",
    "\n",
    "$$\n",
    "C(n,k) = \\left\\lbrace \n",
    "\\begin{array}{ll}\n",
    "0^{n} & \\text{if } k = 0 \\\\\n",
    "1^{n} & \\text{if } k = n \\\\\n",
    "C(n-1,k)\\cdot 0 \\circ \\bar{C}(n-1,k-1)\\cdot 1 & otherwise\n",
    "\\end{array}\n",
    "\\right.\n",
    "$$\n",
    "\n",
    "In order to understand previous recurrence we draw a simple schema:\n",
    "\n",
    "$$\n",
    "\\left.\n",
    "\\begin{array}{ccccc}\n",
    "1^{k-1} & 1 & 0 & 0^{n-k-2} & 0 \\\\\n",
    "1^{k-1} & 0 & 1 & 0^{n-k-2} & 0 \\\\\n",
    " &  &   \\vdots & & \\\\\n",
    "1^{k-1} & 0^{n-k-2} & 1 & 0 & 0 \\\\\n",
    "1^{k-1} & 0^{n-k-2} & 0 & 1 & 0 \\\\\n",
    "&  &   = & & \\\\\n",
    "1^{k-2} & 1 & 0^{n-k-1} & 1 & 0 \\\\\n",
    "\\end{array}\n",
    "\\right\\rbrace = C(n-1,k)\\cdot 0 \\\\\n",
    "$$\n",
    "\n",
    "on the other hand, for the second part:\n",
    "\n",
    "$$\n",
    "\\left.\n",
    "\\begin{array}{ccccc}\n",
    "1^{k-2} & 0 & 0^{n-k-1} & 1 & 1 \\\\\n",
    "&  &   = & & \\\\\n",
    "1^{k-2} & 0^{n-k-1} & 0 & 1 & 1 \\\\\n",
    "1^{k-2} & 0^{n-k-1} & 1 & 0 & 1 \\\\\n",
    "&  &   \\vdots & & \\\\\n",
    "1^{k-2} & 0 & 1 & 0^{n-k-1} & 1 \\\\\n",
    "1^{k-2} & 1 & 0 & 0^{n-k-1} & 1 \\\\\n",
    "\\end{array}\n",
    "\\right\\rbrace = \\bar{C}(n-1,k-1)\\cdot 1\n",
    "$$\n",
    "\n",
    "where *boundary* combinations can be rewritten as:\n",
    "   - $first(C(n-1,k)\\cdot 0) = 1^{k-1} \\, 0^{n-k-1} \\, 1\\, 0 $;\n",
    "   - $last(C(n-1,k)\\cdot 0) = 1^{k-2} \\, 1 \\, 0^{n-k-1} \\, 1\\, 0 $;\n",
    "   - $first(\\bar{C}(n-1,k-1)\\cdot 1) = 1^{k-2} \\, 0 \\, 0^{n-k-1} \\, 1 \\, 1 $;\n",
    "   - $last(\\bar{C}(n-1,k-1)\\cdot 1) = 1^{k-1} \\, 0^{n-k-1} \\, 0 \\, 1 $.\n",
    "   \n",
    "The following is a Pythonic implementation of the above relation, ispired by Ruskey again:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "```python\n",
       "def graycodes_combinations(n, k):\n",
       "\n",
       "    combination = set_all(k)\n",
       "\n",
       "    if not k or k == n: \n",
       "        yield combination\n",
       "        raise StopIteration()\n",
       "\n",
       "    def swap(n, k):\n",
       "        nonlocal combination\n",
       "        i, j = (n-2, n-1) if k < 2 else (k-2, n-1)\n",
       "        combination = toggle_bits(combination, i, j)\n",
       "        yield combination, i, j \n",
       "\n",
       "    def gen(n, k):\n",
       "        if k in range(1, n):\n",
       "            yield from itertools.chain(gen(n-1, k), swap(n, k), neg(n-1, k-1))\n",
       "\n",
       "    def neg(n, k):\n",
       "        if k in range(1, n):\n",
       "            yield from itertools.chain(gen(n-1, k-1), swap(n, k), neg(n-1, k))\n",
       "\n",
       "    yield combination, -1, -1\n",
       "    yield from gen(n, k)\n",
       "\n",
       "```"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "python_code(graycodes_combinations)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "it can be used as follows, showing changing-bits positions too:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "   0b111\t-1\t-1\n",
      "  0b1101\t1\t3\n",
      "  0b1110\t0\t1\n",
      "  0b1011\t0\t2\n",
      " 0b11001\t1\t4\n",
      " 0b11010\t0\t1\n",
      " 0b11100\t1\t2\n",
      " 0b10101\t0\t3\n",
      " 0b10110\t0\t1\n",
      " 0b10011\t0\t2\n",
      "0b110001\t1\t5\n",
      "0b110010\t0\t1\n",
      "0b110100\t1\t2\n",
      "0b111000\t2\t3\n",
      "0b101001\t0\t4\n",
      "0b101010\t0\t1\n",
      "0b101100\t1\t2\n",
      "0b100101\t0\t3\n",
      "0b100110\t0\t1\n",
      "0b100011\t0\t2\n"
     ]
    }
   ],
   "source": [
    "for c, i, j in graycodes_combinations(6,3):\n",
    "    print(\"{:>8}\\t{}\\t{}\".format(bin(c), i, j))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Using *homogeneous transposition* relation\n",
    "\n",
    "In this section we would like to produce a sequence of code such that belong to the *homogeneous transposition* relation pairwise. In order to accomplish that, we unfold the binomial term ${{n-1}\\choose{k-1}}$ and write the following recurrence:\n",
    "$$\n",
    "E(n, k) = \\left\\lbrace\n",
    "\\begin{array}{cc}\n",
    "0^{n} & \\text{if } k = 0\\\\\n",
    "1^{n} & \\text{if } k = n\\\\\n",
    "10^{n-1}\\circ 010^{n-2}\\circ\\ldots\\circ 0^{n-2}10\\circ 0^{n-1}1 & \\text{if } k = 1 \\\\\n",
    "E(n-1,k)\\cdot 0 \\circ \\bar{E}(n-2,k-1)\\cdot 01 \\circ E(n-2, k-2)\\cdot 11 & otherwise\n",
    "\\end{array}\n",
    "\\right.\n",
    "$$\n",
    "\n",
    "In order to understand previous recurrence we draw a simple schema:\n",
    "\n",
    "$$\n",
    "\\left.\n",
    "\\begin{array}{ccccc}\n",
    "1^{k-1} & 1 & 0 & 0^{n-k-2} & 0 \\\\\n",
    "1^{k-1} & 0 & 1 & 0^{n-k-2} & 0 \\\\\n",
    " &  &   \\vdots & & \\\\\n",
    "1^{k-1} & 0^{n-k-2} & 1 & 0 & 0 \\\\\n",
    "1^{k-1} & 0^{n-k-2} & 0 & 1 & 0 \\\\\n",
    "&  &   = & & \\\\\n",
    "1^{k-2} & 1 & 0^{n-k-1} & 1 & 0 \\\\\n",
    "\\end{array}\n",
    "\\right\\rbrace = E(n-1,k)\\cdot 0 \\\\\n",
    "$$\n",
    "\n",
    "for the second part:\n",
    "\n",
    "$$\n",
    "\\left.\n",
    "\\begin{array}{cccccc}\n",
    "1^{k-2} & \\underline{0} & 0^{n-k-2} & \\underline{1} & 1 & 0 \\\\\n",
    "&  &   = & & \\\\\n",
    "1^{k-2} & 0^{n-k-2} & 0 & 1 & 1 & 0 \\\\\n",
    "1^{k-2} & 0^{n-k-2} & 1 & 0 & 1 & 0 \\\\\n",
    "&  &   \\vdots & & & \\\\\n",
    "1^{k-2} & 0 & 1 & 0^{n-k-2} & 1 & 0 \\\\\n",
    "1^{k-2} & 1 & 0 & 0^{n-k-2} & 1 & 0 \\\\\n",
    "\\end{array}\n",
    "\\right\\rbrace = \\bar{E}(n-2,k-1)\\cdot 10 \\\\\n",
    "$$\n",
    "\n",
    "for the third part:\n",
    "\n",
    "$$\n",
    "\\left.\n",
    "\\begin{array}{cccccc}\n",
    "1^{k-2} & \\underline{0} & 0 & 0^{n-k-2} & 1 & \\underline{1} \\\\\n",
    "&  &   = & & & \\\\\n",
    "1^{k-3} & 1 & 0 & 0^{n-k-1} & 1 & 1 \\\\\n",
    "1^{k-3} & 0 & 1 & 0^{n-k-1} & 1 & 1 \\\\\n",
    " &  &   \\vdots & & & \\\\\n",
    "1^{k-3} & 0^{n-k-1} & 1 & 0 & 1 & 1 \\\\\n",
    "1^{k-3} & 0^{n-k-1} & 0 & 1 & 1 & 1 \\\\\n",
    "\\end{array}\n",
    "\\right\\rbrace = E(n-2,k-2)\\cdot 11 \\\\\n",
    "$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "```python\n",
       "def graycodes_combinations_homogeneous(n, k):\n",
       "\n",
       "    combination = set_all(k)\n",
       "\n",
       "    def swap(i, j):\n",
       "        nonlocal combination\n",
       "        combination = toggle_bits(combination, i, j)\n",
       "        yield combination, i, j \n",
       "\n",
       "    def gen(n, k):\n",
       "        if k == 1: \n",
       "            for i in range(n-1): yield from swap(i, i+1)\n",
       "        elif k in range(2, n):\n",
       "            #yield from itertools.chain(gen(n-1, k), swap(k-2, n-3), neg(n-2, k-1), swap(k-2, n-1), gen(n-2, k-2))\n",
       "            yield from itertools.chain(gen(n-1, k), swap(n-1, n-2), neg(n-2, k-1), swap(k-2, n-2), gen(n-2, k-2))\n",
       "\n",
       "    def neg(n, k):\n",
       "        if k == 1: \n",
       "            for i in range(n-1): yield from swap(i, i+1)\n",
       "        elif k in range(2, n):\n",
       "            #yield from itertools.chain(neg(n-2, k-2), swap(k-2, n-1), gen(n-2, k-1), swap(k-2, n-3), neg(n-1, k))\n",
       "            yield from itertools.chain(neg(n-2, k-2), swap(k-2, n-2), gen(n-2, k-1), swap(n-1, n-2), neg(n-1, k))\n",
       "\n",
       "    yield combination, -1, -1\n",
       "    yield from gen(n, k)\n",
       "\n",
       "```"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "python_code(graycodes_combinations_homogeneous)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-1\t-1\t  0b1111\n",
      "4\t3\t 0b10111\n",
      "2\t3\t 0b11011\n",
      "2\t1\t 0b11101\n",
      "0\t1\t 0b11110\n",
      "5\t4\t0b101110\n",
      "0\t1\t0b101101\n",
      "1\t2\t0b101011\n",
      "3\t2\t0b100111\n",
      "2\t4\t0b110011\n",
      "2\t1\t0b110101\n",
      "0\t1\t0b110110\n",
      "3\t2\t0b111010\n",
      "0\t1\t0b111001\n",
      "0\t2\t0b111100\n",
      "6\t5\t0b1011100\n",
      "0\t1\t0b1011111\n",
      "1\t2\t0b1011001\n",
      "1\t3\t0b1010011\n",
      "2\t1\t0b1010101\n",
      "0\t1\t0b1010110\n",
      "4\t3\t0b1001110\n",
      "0\t1\t0b1001101\n",
      "1\t2\t0b1001011\n",
      "3\t2\t0b1000111\n",
      "2\t5\t0b1100011\n",
      "2\t1\t0b1100101\n",
      "0\t1\t0b1100110\n",
      "3\t2\t0b1101010\n",
      "0\t1\t0b1101001\n",
      "0\t2\t0b1101100\n",
      "4\t3\t0b1110100\n",
      "0\t1\t0b1110111\n",
      "1\t2\t0b1110001\n",
      "0\t3\t0b1111000\n",
      "7\t6\t0b10111000\n",
      "0\t1\t0b10111011\n",
      "1\t2\t0b10111101\n",
      "2\t3\t0b10110001\n",
      "1\t4\t0b10100011\n",
      "2\t1\t0b10100101\n",
      "0\t1\t0b10100110\n",
      "3\t2\t0b10101010\n",
      "0\t1\t0b10101001\n",
      "0\t2\t0b10101100\n",
      "5\t4\t0b10011100\n",
      "0\t1\t0b10011111\n",
      "1\t2\t0b10011001\n",
      "1\t3\t0b10010011\n",
      "2\t1\t0b10010101\n",
      "0\t1\t0b10010110\n",
      "4\t3\t0b10001110\n",
      "0\t1\t0b10001101\n",
      "1\t2\t0b10001011\n",
      "3\t2\t0b10000111\n",
      "2\t6\t0b11000011\n",
      "2\t1\t0b11000101\n",
      "0\t1\t0b11000110\n",
      "3\t2\t0b11001010\n",
      "0\t1\t0b11001001\n",
      "0\t2\t0b11001100\n",
      "4\t3\t0b11010100\n",
      "0\t1\t0b11010111\n",
      "1\t2\t0b11010001\n",
      "0\t3\t0b11011000\n",
      "5\t4\t0b11101000\n",
      "0\t1\t0b11101011\n",
      "1\t2\t0b11101101\n",
      "2\t3\t0b11100001\n",
      "0\t4\t0b11110000\n"
     ]
    }
   ],
   "source": [
    "for c, i, j in graycodes_combinations_homogeneous(8,4):\n",
    "    print('{}\\t{}\\t{:>8}'.format(i, j, bin(c),))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "<a rel=\"license\" href=\"http://creativecommons.org/licenses/by-nc/4.0/\"><img alt=\"Creative Commons License\" style=\"border-width:0\" src=\"https://i.creativecommons.org/l/by-nc/4.0/88x31.png\" /></a><br /><span xmlns:dct=\"http://purl.org/dc/terms/\" property=\"dct:title\">Gray codes tutorial</span> by <a xmlns:cc=\"http://creativecommons.org/ns#\" href=\"massimo.nocentini@unifi.it\" property=\"cc:attributionName\" rel=\"cc:attributionURL\">Massimo Nocentini</a> is licensed under a <a rel=\"license\" href=\"http://creativecommons.org/licenses/by-nc/4.0/\">Creative Commons Attribution-NonCommercial 4.0 International License</a>.<br />Based on a work at <a xmlns:dct=\"http://purl.org/dc/terms/\" href=\"https://github.com/massimo-nocentini/competitive-programming/blob/master/tutorials/graycodes.ipynb\" rel=\"dct:source\">https://github.com/massimo-nocentini/competitive-programming/blob/master/tutorials/graycodes.ipynb</a>."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}