Chapter 7 - Combinatorial Search and Heuristic Methods.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 7: Combinatorial Search and Heuristic Methods (Completed 5/19: 26%)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below is a general purpose Backtracking routine, adapted into Python from the book's C implementation, that will be used in some of the exercises."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def backtrack(A, k, **data):\n",
    "    if is_a_solution(A, k, **data):\n",
    "        process_solution(A,k, **data)\n",
    "    else:\n",
    "        k += 1\n",
    "        candidates = construct_candidates(A,k, **data)\n",
    "        for i, _ in enumerate(candidates):\n",
    "            A.append(candidates[i])\n",
    "            make_move(A, k, **data)\n",
    "            backtrack(A, k, **data)\n",
    "            unmake_move(A, k, **data)\n",
    "            A.pop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.1 [3]\n",
    "\n",
    "A *derangement* is a permutation $p$ of $\\{1, . . . , n\\}$ such that no item is in its proper position, i.e. $p_i \\neq i$ for all $1 \\leq i \\leq n$. Write an efficient backtracking program with pruning that constructs all the derangements of $n$ items."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "For simplicity, the program computes the derangements of numbers $\\{0, . . . , n-1\\}$.\n",
    "\n",
    "A closed form expression for the number of derangements, notated as $!n$, from [Wikipedia](http://www.wikiwand.com/en/Derangement), is given by:\n",
    "\n",
    "$$ !n = \\left[ \\frac{n!}{e} \\right] = \\left \\lfloor \\frac{n!}{e} + \\frac{1}{2} \\right \\rfloor$$\n",
    "\n",
    "where $[x]$ is the nearest integer function. Therefore this number grows proportionally with $n!$, the number of permutations.\n",
    "\n",
    "This problem is very similar to constructing permutations, a partial solution to which is provided in the text. However, we must ensure that we don't insert number $i$ at position $i$. Therefore we include the check `(i != k)` when screening potential candidates in the `construct_candidates` function. This effectively prunes partial solutions that are doomed to fail, rather than putting such a check in the `is_a_solution`, which would require a linear scan through all $!n$ solutions checking if `A[i] == i`. This indeed would be exhaustive."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 0, 3, 2]\n",
      "Solution number: 1\n",
      "[1, 2, 3, 0]\n",
      "Solution number: 2\n",
      "[1, 3, 0, 2]\n",
      "Solution number: 3\n",
      "[2, 0, 3, 1]\n",
      "Solution number: 4\n",
      "[2, 3, 0, 1]\n",
      "Solution number: 5\n",
      "[2, 3, 1, 0]\n",
      "Solution number: 6\n",
      "[3, 0, 1, 2]\n",
      "Solution number: 7\n",
      "[3, 2, 0, 1]\n",
      "Solution number: 8\n",
      "[3, 2, 1, 0]\n",
      "Solution number: 9\n"
     ]
    }
   ],
   "source": [
    "## Problem-specific functions  \n",
    "def construct_candidates(A, k, n, V, m):\n",
    "    candidates = []\n",
    "    for i in range(n):\n",
    "        if (V[i] == False) and (i != k):\n",
    "            candidates.append(i)\n",
    "    return candidates\n",
    "\n",
    "def make_move(A, k, n, V, m):\n",
    "    V[A[k]] = True\n",
    "    \n",
    "def unmake_move(A, k, n, V, m):\n",
    "    V[A[k]] = False\n",
    "\n",
    "def is_a_solution(A, k, n, V, m):\n",
    "    return k == n - 1\n",
    "\n",
    "def process_solution(A, k, n, V, m):\n",
    "    print(A)\n",
    "    m[0] += 1\n",
    "    print(\"Solution number:\", m[0])\n",
    "    \n",
    "def generate_derangements(n):\n",
    "    A = []\n",
    "    V = []\n",
    "    m = [0]   #number of solutions\n",
    "    \n",
    "    for i in range(n):\n",
    "        V.append(False)\n",
    "        \n",
    "    backtrack(A, -1, n = n, V = V, m = m)\n",
    "\n",
    "generate_derangements(4)\n",
    "\n",
    "#No number is in the position equal to its value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.2 [4]\n",
    "\n",
    "*Multisets* are allowed to have repeated elements. A multiset of $n$ items may thus have fewer than $n!$ distinct permutations. For example, $\\{1, 1, 2, 2\\}$ has only six different permutations: $\\{1, 1, 2, 2\\}$, $\\{1, 2, 1, 2\\}$, $\\{1, 2, 2, 1\\}$, $\\{2, 1, 1, 2\\}$, $\\{2, 1, 2, 1\\}$, and $\\{2, 2, 1, 1\\}$. Design and implement an efficient algorithm for constructing all\n",
    "permutations of a multiset."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "I originally tried to solve this problem by enumerating permutations of the index and pruning them appropriately. (Skip this paragaph if you want.) For example, $S = \\{1, 1, 2, 2\\}$ contains 4 numbers, so permutations of the numbers 1 through 4 will correspond to permutations of $S$. The only problem is that some of these index permutations will correspond to identical set permutations, due to the repeated elements. For example, both index permutations $\\{1, 3, 2, 4\\}$ and $\\{1, 4, 2, 3 \\}$ produce the set permutation $\\{1, 2, 1, 2\\}$. However, we may note that only one of these satisfies the condition that indices corresponding to identical set elements are in sorted order. Specifically, both indices $3$ and $4$ correspond to the number $2$ in the set $S$. So if we require that such numbers be in sorted order, then only one of these index permutations is valid, $\\{1, 3, 2, 4\\}$. However, I was unable to encode this without using a \"stack\" data structure. Specifically, for set-values already included, a second auxilliary data structure would be needed to record what index was used most recently that corresponds to this value. (The first data structure is a bit vector for included indices.) For example, when adding index $3$ to the partial solution $\\{1, 4, 2\\}$, we would need check that $S[3] = 2$ was already included using index $4$, and since $3 < 4$ this would break our requirement that indices that correspond to equal set values be in sorted order. The problem is how to implement the `unmake_move` function when there are more than 2 identical elements. For example, if there are 5 3's in the set $S$, then our second auxiliary data structure would essentially have to record the order in which these 5 different indices were added. This could be done with a stack. However, I was able to find a more elementary and direct solution to the problem.\n",
    "\n",
    "To solve this problem, we can compute a histogram-like structure that tells us how many more times we can include a given value. For example, say you have 3 unique numbers, like $S = [1, 1, 2, 2, 2, 7, 7]$. We can turn this into two arrays $H = [2, 3, 2]$ and $I = [1, 2, 7]$, where the first tells you how many of each number you have, and the second is what the number is. Together, these form a sort of histogram, with $I$ the x values and $H$ the y values.\n",
    "\n",
    "At each iteration in the backtracking algorithm, the potential candidates for the next position in our solution vector $A$ are any index from $0$ to $m-1$ such that $H[i] \\neq 0$, where $m$ is the number of unique values in $S$. When a number $i$ is added to $A$, we decrement $H[i]$ by one to indicate that we have one less of that number available for future positions. To undo this, we increment $H[i]$ by one.\n",
    "\n",
    "Interestingly, although this solution is conceptually different from how the permutation problem is treated, it may in fact be a generalization. The permutation problem uses a bit vector to indicate what indices from $1$ to $n$ have already been included. This is analogous to our $H$ array, only in the permutation problem we know that each number appears exactly once, and so True/False values can be used instead of 1's and 0's. Also, there is no need for an $I$ array in the permutation case because the value and the index are equal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The set: [1, 1, 2, 2] \n",
      "\n",
      "Solution number: 1\n",
      "Permutation; [1, 1, 2, 2]\n",
      "\n",
      "Solution number: 2\n",
      "Permutation; [1, 2, 1, 2]\n",
      "\n",
      "Solution number: 3\n",
      "Permutation; [1, 2, 2, 1]\n",
      "\n",
      "Solution number: 4\n",
      "Permutation; [2, 1, 1, 2]\n",
      "\n",
      "Solution number: 5\n",
      "Permutation; [2, 1, 2, 1]\n",
      "\n",
      "Solution number: 6\n",
      "Permutation; [2, 2, 1, 1]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "## Problem-specific functions  \n",
    "def construct_candidates(A, k, n, H, I, m):\n",
    "    candidates = []\n",
    "    for i, _ in enumerate(I):\n",
    "        if H[i] != 0:\n",
    "            candidates.append(i)       \n",
    "    return candidates\n",
    "\n",
    "def make_move(A, k, n, H, I, m):\n",
    "    H[A[k]] -= 1\n",
    "    \n",
    "def unmake_move(A, k, n, H, I, m):\n",
    "    H[A[k]] += 1\n",
    "\n",
    "def is_a_solution(A, k, n, H, I, m):\n",
    "    return k == n - 1\n",
    "\n",
    "def process_solution(A, k, n, H, I, m):\n",
    "    m[0] += 1\n",
    "    Solution = []\n",
    "    for i, _ in enumerate(A):\n",
    "        Solution.append(I[A[i]])\n",
    "        \n",
    "    print(\"Solution number:\", m[0])\n",
    "    print('Permutation;', Solution)\n",
    "    print()\n",
    " \n",
    "def construct_histogram(S):\n",
    "    H = []\n",
    "    I = []\n",
    "    \n",
    "    for i, _ in enumerate(S):\n",
    "        if i == 0 or S[i] > S[i - 1]: #New number\n",
    "            I.append(S[i])\n",
    "            H.append(1)\n",
    "        else:\n",
    "            H[-1] += 1\n",
    "    return H, I\n",
    "\n",
    "def generate_multiset_permutations(S):\n",
    "    S.sort()\n",
    "    A = []\n",
    "    H, I = construct_histogram(S)\n",
    "    m = [0]     #number of solutions\n",
    "    n = len(S)\n",
    "\n",
    "    backtrack(A, -1, n = n, H = H, I = I, m = m)\n",
    "\n",
    "S = [1, 1, 2, 2]\n",
    "print('The set:', S, '\\n')\n",
    "generate_multiset_permutations(S)\n",
    "\n",
    "# Possible Multisets from the given example:\n",
    "#{1,1,2,2}\n",
    "#{1,2,1,2}\n",
    "#{1,2,2,1}\n",
    "#{2,1,1,2}\n",
    "#{2,1,2,1}\n",
    "#{2,2,1,1}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Combinatorial Optimization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Interview Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For this section I will not use the general purpose backtracking algorithm at the beginning of this notebook, but rather will write the algorithms from scratch as if I was in an \"interview\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.14 [4]\n",
    "\n",
    "Write a function to find all permutations of the letters in a particular string."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "If we may use Python's dictionary structure, we can convert the string into a dictionary mapping each letter to the number of times it appears in the string. Think of this as a histogram. We can then use a backtracking algorithm to sucessively build up solution strings by taking letters off the histogram."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ello\n",
      "elol\n",
      "eoll\n",
      "lelo\n",
      "leol\n",
      "lleo\n",
      "lloe\n",
      "loel\n",
      "lole\n",
      "oell\n",
      "olel\n",
      "olle\n"
     ]
    }
   ],
   "source": [
    "def string_to_histogram(s):\n",
    "    D = {}\n",
    "    for c in s:\n",
    "        if c in D:\n",
    "            D[c] += 1\n",
    "        else:\n",
    "            D[c] = 1\n",
    "    return D\n",
    "\n",
    "def string_backtrack(A, k, D, n, m):\n",
    "    if k == n - 1:\n",
    "        m[0] += 1\n",
    "        #print('Solution', m[0])  #Uncomment to count solutions\n",
    "        print(''.join(A))\n",
    "    else:\n",
    "        k += 1\n",
    "        candidates = construct_candidates(D)\n",
    "        for c in candidates:\n",
    "            A.append(c)\n",
    "            D[c] -= 1\n",
    "            string_backtrack(A, k, D, n, m)\n",
    "            D[c] += 1\n",
    "            A.pop()\n",
    "\n",
    "def construct_candidates(D):\n",
    "    candidates = []\n",
    "    for s in D:\n",
    "        if D[s] != 0:\n",
    "            candidates.append(s)\n",
    "    return candidates\n",
    "            \n",
    "def string_permutations(s):\n",
    "    A = []\n",
    "    k = -1\n",
    "    D = string_to_histogram(s)\n",
    "    n = len(s)\n",
    "    m = [0]\n",
    "     \n",
    "    string_backtrack(A, k, D, n, m)\n",
    "\n",
    "string_permutations('ello')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.15 [4]\n",
    "\n",
    "Implement an efficient algorithm for listing all $k$-element subsets of $n$ items."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "I assume that all $n$ items are distinguishable. We can then number the items from $0$ to $n-1$ and enumerate all subsets of size $k$ of these numbers. We can do this using a backtracking algorithm. An array $A$ will hold our partial solutions, and we'll use a bit vector to record which items have already been included. Candidate values to add next are those values which haven't yet been included, which is a constant time lookup with the bit vector.\n",
    "\n",
    "We also require that the element being added be greater than the previous element. For example, of all the permutations that correspond to the size-3 subset $\\{1, 2, 4\\}$, the rest of them will at some point have broken the rule that the additional element was lower than the previous one. So this condition eliminates any equivalent permutations of the same subset showing up, and therefore significantly prunes our search.\n",
    "\n",
    "NOTE: A elementary but still recursive function for doing this was done as a subproblem for problem 4.10. It was quite challenging, so it is remarkable that using backtracking the problem becomes somewhat easy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2]\n",
      "[0, 1, 3]\n",
      "[0, 1, 4]\n",
      "[0, 2, 3]\n",
      "[0, 2, 4]\n",
      "[0, 3, 4]\n",
      "[1, 2, 3]\n",
      "[1, 2, 4]\n",
      "[1, 3, 4]\n",
      "[2, 3, 4]\n"
     ]
    }
   ],
   "source": [
    "# Note that j plays the role of k\n",
    "# compared to most of the other\n",
    "# backtracking implementations here\n",
    "\n",
    "def k_subset_backtrack(A, j, n, k, V):\n",
    "    if j == k - 1:\n",
    "        print(A)\n",
    "    else:\n",
    "        j += 1\n",
    "        candidates = construct_candidates(A, j, n, k, V)\n",
    "        for c in candidates:\n",
    "            A.append(c)\n",
    "            V[c] = True\n",
    "            k_subset_backtrack(A, j, n, k, V)\n",
    "            V[c] = False\n",
    "            A.pop()\n",
    "\n",
    "def construct_candidates(A, j, n, k, V):\n",
    "    candidates = []\n",
    "    for i, v in enumerate(V):\n",
    "        if v == False and ((j == 0) or (A[j-1] < i)):\n",
    "            candidates.append(i)\n",
    "    return candidates\n",
    "            \n",
    "def k_subsets(n, k):\n",
    "    A = []\n",
    "    V = []\n",
    "    j = -1\n",
    "    \n",
    "    for i in range(n): #Initialize bit-vector\n",
    "        V.append(False)\n",
    "        \n",
    "    k_subset_backtrack(A, j, n, k, V)\n",
    "    \n",
    "k_subsets(5, 3)    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 7.16 [5]\n",
    "\n",
    "An anagram is a rearrangement of the letters in a given string into a sequence of dictionary words, like *Steven Skiena* into *Vainest Knees*. Propose an algorithm to construct all the anagrams of a given string."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "This problem is similar to enumerating all the perumutations of a set of $n$ numbers, where $n$ is the length of the string, but for 3 complications. Strings are multisets, meaning they can have repeated elements. Permuting equal letters doesn't change a word, so unless we accound for this, the same anagram will appear multiple times. The second complication is that anagrams are free to include differing amounts of words separated by spaces, as long as they contain the same set of letters.\n",
    "\n",
    "The third complication is the requirement that the resulting strings be dictionary words.\n",
    "\n",
    "To construct the anagrams, we will convert the original string into a histogam-like structure that will track how many more times we may use each letter. \"Space\" will also be an option unless the previously added character was also a \"space\". We will use a backtracking algorithm to recursively extend partial string vectors $A$ one character at a time, using the histogram to track what characters remain available for insertion.\n",
    "\n",
    "To enforce the requirement that the words be found in the dictionary, each time we add a \"space\" we will check if the word is contained in a list of dictionary words, found in `'Other/Dictionary_words.txt'`. The `is_word()` function makes use of the `bisect` module to implement a binary search. When we have found a potential solution, we use the `is_word()` function again to check if the last word in the solution is valid.\n",
    "\n",
    "The program implemented below works, but takes about a minute to run on the string 'steven skien', and is too slow to run on 'steven skiena'.\n",
    "\n",
    "One important area where the program can be improved is the `is_word()` function. Currently a binary search is performed on a list of valid words that originally was stored at `/usr/share/dict/words` on my computer. However, this list **does not contain plurals** even though it contains 235886 words. I found a list of dictionary words online that contained 354986 words, but many of them did not seem to be valid words, like \"wl\", and many other two-letter combinations. For example, the word \"pillow\" produces 33 or 2498 different anagrams depending on which of these two dictionaries is used. I opted for the smaller one.\n",
    "\n",
    "Instead of manually performing a binary search on a list of dictionary words, I could have used a specialized spell checker library that would probably provide better and faster results, but I am not sure what modules GitHub has available on their system."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "235886\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import bisect\n",
    "\n",
    "# Index function code from\n",
    "# bisect module page\n",
    "def index(a, x):\n",
    "    'Locate the leftmost value exactly equal to x'\n",
    "    i = bisect.bisect_left(a, x)\n",
    "    if i != len(a) and a[i] == x:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "def is_word(x):\n",
    "    return index(dictionary_words, x)\n",
    "\n",
    "with open('Other/Dictionary_words.txt', 'r') as file:\n",
    "    dictionary_words = [line.rstrip() for line in file]\n",
    "dictionary_words.sort()\n",
    "\n",
    "print(len(dictionary_words))\n",
    "is_word('all')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pillows\n",
      "{'l': 2, 'i': 1, 'p': 1, 'o': 1, 's': 1, 'w': 1}\n",
      "Anagram 1: lip slow\n",
      "Anagram 2: lip sowl\n",
      "Anagram 3: lisp low\n",
      "Anagram 4: lisp owl\n",
      "Anagram 5: lis plow\n",
      "Anagram 6: low lisp\n",
      "Anagram 7: low slip\n",
      "Anagram 8: ill wops\n",
      "Anagram 9: plow lis\n",
      "Anagram 10: plow sil\n",
      "Anagram 11: pill sow\n",
      "Anagram 12: poll wis\n",
      "Anagram 13: pow sill\n",
      "Anagram 14: po swill\n",
      "Anagram 15: owl lisp\n",
      "Anagram 16: owl slip\n",
      "Anagram 17: ow spill\n",
      "Anagram 18: slip low\n",
      "Anagram 19: slip owl\n",
      "Anagram 20: slow lip\n",
      "Anagram 21: sill pow\n",
      "Anagram 22: sill wop\n",
      "Anagram 23: sil plow\n",
      "Anagram 24: spill ow\n",
      "Anagram 25: spill wo\n",
      "Anagram 26: sop will\n",
      "Anagram 27: sowl lip\n",
      "Anagram 28: sow pill\n",
      "Anagram 29: swill po\n",
      "Anagram 30: will sop\n",
      "Anagram 31: wis poll\n",
      "Anagram 32: wops ill\n",
      "Anagram 33: wop sill\n",
      "Anagram 34: wo spill\n",
      "CPU times: user 101 ms, sys: 2.35 ms, total: 103 ms\n",
      "Wall time: 104 ms\n"
     ]
    }
   ],
   "source": [
    "# A = partial solution string\n",
    "# D = dictionary \"histogram\" of remaining letters\n",
    "# m = number of letters currently in solution string\n",
    "# n = number of letters in original string\n",
    "# sol = solution number\n",
    "\n",
    "def anagram_backtracking(A, D, m, n, sol):\n",
    "    if m == n and last_word_in_dict(A, D, m, n, sol):\n",
    "        sol[0] += 1\n",
    "        print('Anagram %s:' % sol[0], ''.join(A))\n",
    "    else:\n",
    "        candidates = construct_candidates_anagram(A, D, m, n, sol)\n",
    "        for c in candidates:\n",
    "            A.append(c)\n",
    "            if c != ' ':\n",
    "                D[c] -= 1\n",
    "                m += 1\n",
    "            anagram_backtracking(A, D, m, n, sol)\n",
    "            if c != ' ':\n",
    "                D[c] += 1\n",
    "                m -= 1\n",
    "            A.pop()\n",
    "\n",
    "def construct_candidates_anagram(A, D, m, n, sol):\n",
    "    candidates = []\n",
    "    for c, h in D.items():\n",
    "        if h != 0:\n",
    "            candidates.append(c)    \n",
    "    if m != 0 and A[-1] != ' ': # Consider 'space'\n",
    "        if last_word_in_dict(A, D, m, n, sol):\n",
    "            candidates.append(' ')\n",
    "    return candidates\n",
    "\n",
    "def last_word_in_dict(A, D, m, n, sol):\n",
    "    s = 0 # Position of previous 'space'\n",
    "    for i in range(len(A)):\n",
    "        if A[-(i+1)] == ' ':\n",
    "            s = i\n",
    "            break\n",
    "    word = ''.join(A[-s:])\n",
    "    if len(word) == 1:\n",
    "        return (word == 'a' or word == 'i')\n",
    "    else:\n",
    "        #return word in dictionary_words\n",
    "        return is_word(word)\n",
    "         \n",
    "def construct_histogram(s):\n",
    "    D = {}\n",
    "    for c in s:\n",
    "        if c == ' ': # Ignore spaces\n",
    "            continue\n",
    "        if c in D:\n",
    "            D[c] += 1\n",
    "        else:\n",
    "            D[c] = 1\n",
    "    return D\n",
    "\n",
    "def find_anagrams(s):\n",
    "    s = s.lower().replace(' ', '')\n",
    "    print(s)\n",
    "    A = []\n",
    "    D = construct_histogram(s)\n",
    "    m = 0\n",
    "    n = len(s)\n",
    "    sol = [0]\n",
    "    print(D)\n",
    "    anagram_backtracking(A, D, m, n, sol)\n",
    "\n",
    "%time find_anagrams('pillows')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7.17 [5] Unfinished\n",
    "\n",
    "Telephone keypads have letters on each numerical key. Write a program that generates all possible words resulting from translating a given digit sequence (e.g., 145345) into letters."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "keypad = {1 : ['a', 'b', 'c'],\n",
    "          2 : ['d', 'e', 'f']}\n",
    "\n",
    "def keypad_backtracking(A, n, D, m):\n",
    "    if n == m:\n",
    "        print(''.join(A))\n",
    "    else:\n",
    "        candidates = keypad_construct_candidates(A, n, D, m)\n",
    "        for c in candidates:\n",
    "            A.append(c)\n",
    "            keypad_backtracking(A, n, D, m)\n",
    "            A.pop()\n",
    "            \n",
    "#def keypad_construct_candidates(A, n, D, m):\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  }
 ],
 "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
}