{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. Write a generator function that given a string, generates all [permutations](https://en.wikipedia.org/wiki/Permutation) of that string. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "This generator is interesting for calling itself [recursively](https://en.wikipedia.org/wiki/Recursion).\n",
    "\n",
    "The first time you come across recursion, it blows your mind, then you have an epiphany of the power of the technique. It makes some problems easy to code, as here. Lars had two epiphanies when he was 19. One of them was recursion."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def permutate(collection):\n",
    "    '''Yields all the permutations of the collection.\n",
    "    The collection must be sliceable.'''\n",
    "    for i, item in enumerate(collection):\n",
    "        subcollection = collection[:i] + collection[i+1:]\n",
    "        if subcollection:\n",
    "            for permutation in permutate(subcollection):\n",
    "                yield item + permutation\n",
    "        else:\n",
    "            yield item"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['RGB', 'RBG', 'GRB', 'GBR', 'BRG', 'BGR']"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(permutate('RGB'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compare that to how permutations from itertools works."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from itertools import permutations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('R', 'G', 'B'),\n",
       " ('R', 'B', 'G'),\n",
       " ('G', 'R', 'B'),\n",
       " ('G', 'B', 'R'),\n",
       " ('B', 'R', 'G'),\n",
       " ('B', 'G', 'R')]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(permutations('RGB'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(2, 3, 5), (2, 5, 3), (3, 2, 5), (3, 5, 2), (5, 2, 3), (5, 3, 2)]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(permutations([2, 3, 5]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[((2,), (3,), (5,)),\n",
       " ((2,), (5,), (3,)),\n",
       " ((3,), (2,), (5,)),\n",
       " ((3,), (5,), (2,)),\n",
       " ((5,), (2,), (3,)),\n",
       " ((5,), (3,), (2,))]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(permutations([(2,), (3,), (5,)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(2,)]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(permutations([2]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now I make permutate have the same output as permutations from itertools.\n",
    "\n",
    "This code is written for readability, not for speed. Concatenation is slow.\n",
    "It would probably be faster to use the extend method of list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def permutate(collection):\n",
    "    for i, item in enumerate(collection):\n",
    "        subcollection = collection[:i] + collection[i+1:]\n",
    "        if subcollection:\n",
    "            for permutation in permutate(subcollection):\n",
    "                yield (item,) + permutation\n",
    "        else:\n",
    "            yield (item,)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'All tests passed'"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Ensure that my permutate yields the same output as permutations from itertools.\n",
    "# My tests are nowhere exhaustive.\n",
    "\n",
    "test_cases = (\n",
    "    'RGB',\n",
    "    [(2,), (3,), (5,)],\n",
    "    [2, 3, 5],\n",
    "    [2],\n",
    ")\n",
    "\n",
    "def test():\n",
    "    for collection in test_cases:\n",
    "        assert list(permutate(collection)) == list(permutations(collection)), (\n",
    "            collection, list(permutate(collection)), list(permutations(collection)))\n",
    "    return 'All tests passed'\n",
    "\n",
    "test()"
   ]
  }
 ],
 "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}