Exercises 6.1.1 and 6.1.3 and their related problems (from Ch.6 Frequent Itemsets).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Contents:\n",
    "- <a href='#exercise-6-1-1'>Exercise 6.1.1</a>\n",
    "- <a href='#exercise-6-1-2'>Exercise 6.1.2</a>\n",
    "- <a href='#exercise-6-1-3'>Exercise 6.1.3</a>\n",
    "- <a href='#exercise-6-1-5'>Exercise 6.1.5</a>\n",
    "- <a href='#exercise-6-1-6'>Exercise 6.1.6</a>\n",
    "- <a href='#exercise-6-2-5'>Exercise 6.2.5</a>\n",
    "- <a href='#exercise-6-2-6'>Exercise 6.2.6 (A-Priori Algorithm)</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "<a id='exercise-6-1-1'></a>\n",
    "# Exercise 6.1.1:\n",
    "Suppose there are 100 items, numbered 1 to 100, and also 100 baskets, also numbered 1 to 100. Item `i` is in basket `b` if and only if `i` divides `b` with no remainder. Thus, item 1 is in all the baskets, item 2 is in all fifty of the even-numbered baskets, and so on. Basket 12 consists of items {1,2,3,4,6,12}, since these are all the integers that divide 12. Answer the following questions:\n",
    "\n",
    "(a) If the support threshold is 5, which items are frequent?\n",
    "\n",
    "(b) If the support threshold is 5, which pairs of items are frequent?\n",
    "\n",
    "(c) What is the sum of the sizes of all the baskets?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution:\n",
    "\n",
    "(a) Item `i` is in basket `b` if `i` is a factor of `b`. In other words, `i` is in basket `b` if and only if there exists a constant integer `k`>=1 such that `b=k*i`. As a result, item `i` is found in 5 or more baskets if `100/i >=5`. Therefore items {1},{2},...,{20} represent the frequent singletons."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Can get the set of frequent pairs, by explicitly counting the support set of each pair and returning those whose counts are greater than 5. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 229,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# baskets[i] gives the list of baskets in which item i is in contained\n",
    "baskets = {}\n",
    "for i in range(1,101):\n",
    "    baskets[i] = []\n",
    "    k = 1\n",
    "    while (i*k) <= 100:\n",
    "        baskets[i].append(k*i)\n",
    "        k += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 230,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 2) (1, 3) (1, 4) (1, 5) (1, 6) (1, 7) (1, 8) (1, 9) (1, 10) (1, 11) (1, 12) (1, 13) (1, 14) (1, 15) (1, 16) (1, 17) (1, 18) (1, 19) (1, 20) (2, 3) (2, 4) (2, 5) (2, 6) (2, 7) (2, 8) (2, 9) (2, 10) (2, 12) (2, 14) (2, 16) (2, 18) (2, 20) (3, 4) (3, 5) (3, 6) (3, 9) (3, 12) (3, 15) (3, 18) (4, 5) (4, 6) (4, 8) (4, 10) (4, 12) (4, 16) (4, 20) (5, 10) (5, 15) (5, 20) (6, 9) (6, 12) (6, 18) (7, 14) (8, 16) (9, 18) (10, 20)\n"
     ]
    }
   ],
   "source": [
    "# finding frequent pairs using a nested loop to select the pairs (i,j) which appear in 5 or more baskets\n",
    "for i in range(1,20): # these are the only singletons which are frequent\n",
    "    for j in range(i+1,21):\n",
    "        commonbask = [b for b in baskets[i] if b in baskets[j]]\n",
    "        if len(commonbask) >= 5:\n",
    "            print (i,j),"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(c) Define, `num_factors(b)` as the number of factors that b has. Then sum of the sizes all baskets = `sum(num_factors(b), b=1,2,...,20)`.\n",
    "\n",
    "So, I didn't feel like thinking about how to grab prime factors of a number myself, so I stackoverflow'ed this. [Here](http://stackoverflow.com/questions/16996217/prime-factorization-list) is simple function to extract the prime factors of a list (it essentially follows how one would find prime factors by hand). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def primes(n):\n",
    "    primfac = []\n",
    "    d = 2\n",
    "    while d*d <= n:\n",
    "        while (n % d) == 0:\n",
    "            primfac.append(d)  # supposing you want multiple factors repeated\n",
    "            n /= d\n",
    "        d += 1\n",
    "    if n > 1:\n",
    "        primfac.append(n)\n",
    "    return primfac"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# create dictionaries for prime factors of baskets 1,2,...,100\n",
    "primefactors = {}\n",
    "for b in range(1,101):\n",
    "    # initializing the dictionary for each basket b\n",
    "    primefactors[b] = {fac:0 for fac in primes(b)}\n",
    "    for key in primes(b):\n",
    "        primefactors[b][key] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{2: 2, 3: 1}"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# for example, the prime factorization of 12 = 2^2 * 3\n",
    "primefactors[12]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To get the number of factors of 12, we add 1 to each of the replications of its factors and apply the multiplication rule. So 12 has (2+1)*(1+1)=6 factors in total."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# to get number of factors, we add 1 to each rep of factor and apply multiplication rule\n",
    "def num_factors(b):\n",
    "    numfac = 1\n",
    "    for fac,reps in primefactors[b].items():\n",
    "        numfac *= reps + 1\n",
    "    return numfac"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "num_factors(12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# sum of the sizes of all baskets\n",
    "sizeofbaskets = [num_factors(b) for b in range(1,101)]\n",
    "totalsize = sum(sizeofbaskets)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "482"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "totalsize"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='exercise-6-1-2'></a>\n",
    "# Exercise 6.1.2\n",
    "For the item-basket data of Exercise 6.1.1, which basket is the largest?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# the largest baskets hav 12 items\n",
    "max(sizeofbaskets)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "60\n",
      "72\n",
      "84\n",
      "90\n",
      "96\n"
     ]
    }
   ],
   "source": [
    "# these baskets are\n",
    "for b in range(1,101):\n",
    "    if num_factors(b) == 12:\n",
    "        print b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='exercise-6-1-3'></a>\n",
    "# Exercise 6.1.3\n",
    "Suppose there are 100 items, numbered 1 to 100, and also 100 baskets, also numbered 1 to 100. Item `i` is in basket `b` if and only if `b` divides `i` with no remainder. For example, basket 12 consists of items {12,24,36,48,60,72,84,96}. Repeat Exercise 6.1.1 for this data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Solution\n",
    "\n",
    "(a) Basket `b` consists of items which are multiples of `b`. Alternatively, item `i` is in basket `b` if `b` is a factor of `i`. Thus, item `i` is frequent if it has at least 5 factors <= 100."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# List of frequent items\n",
    "L1 = [b for b in range(1,101) if num_factors(b)>=5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12 16 18 20 24 28 30 32 36 40 42 44 45 48 50 52 54 56 60 63 64 66 68 70 72 75 76 78 80 81 84 88 90 92 96 98 99 100\n"
     ]
    }
   ],
   "source": [
    "for b in L1:\n",
    "    print b,"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(b) Clearly, `(i,j)` represent a frequent pair if `i` and `j` share at least 5 common factors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def lexorders_ofexp(b):\n",
    "    \"\"\"\n",
    "    This function returns the lexicographic ordering of the exponents\n",
    "    of the prime factors of b. We can use this to get all the factors\n",
    "    of b.\n",
    "    \"\"\"\n",
    "    n = len(primefactors[b])\n",
    "    ati = primefactors[b].values()\n",
    "    foo = []\n",
    "    if n == 1:\n",
    "        for j in range(ati[0]+1):\n",
    "            foo.append([j])\n",
    "    if n == 2:\n",
    "        i = 0\n",
    "        while i < ati[0]+1:\n",
    "            j = 0\n",
    "            while j < ati[1]+1:\n",
    "                foo.append([i,j])\n",
    "                j+=1\n",
    "            i+=1\n",
    "    if n == 3:\n",
    "        i = 0\n",
    "        while i < ati[0]+1:\n",
    "            j = 0\n",
    "            while j < ati[1]+1:\n",
    "                k = 0\n",
    "                while k < ati[2]+1:\n",
    "                    foo.append([i,j,k])\n",
    "                    k+=1\n",
    "                j+=1\n",
    "            i+=1\n",
    "    return foo        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# getting all factors of b from its prime factors\n",
    "def factors(b):\n",
    "    facs = []\n",
    "    exps = lexorders_ofexp(b)\n",
    "    for i in range(num_factors(b)):\n",
    "        bar = 1 # this also takes care of base case factors(1)\n",
    "        for el,key in enumerate(primefactors[b].keys()):\n",
    "            bar *= int(key**exps[i][el])\n",
    "        facs.append(bar)\n",
    "    return facs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def num_commonfactors(b1,b2):\n",
    "    foo = factors(b1)\n",
    "    bar = factors(b2)\n",
    "    return len([el for el in foo if el in bar])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 9, 2, 6, 18, 4, 12, 36, 8, 24, 72]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factors(72)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 2, 6, 4, 12]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factors(12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 2, 6, 4, 12]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# common factors\n",
    "[el for el in factors(12) if el in factors(72)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "num_commonfactors(12,72)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### We are now ready to grab the frequent pairs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(12, 24) (12, 36) (12, 48) (12, 60) (12, 72) (12, 84) (12, 96) (16, 32) (16, 48) (16, 64) (16, 80) (16, 96) (18, 36) (18, 54) (18, 72) (18, 90) (20, 40) (20, 60) (20, 80) (20, 100) (24, 36) (24, 48) (24, 60) (24, 72) (24, 84) (24, 96) (28, 56) (28, 84) (30, 60) (30, 90) (32, 48) (32, 64) (32, 80) (32, 96) (36, 48) (36, 54) (36, 60) (36, 72) (36, 84) (36, 90) (36, 96) (40, 60) (40, 80) (40, 100) (42, 84) (44, 88) (45, 90) (48, 60) (48, 64) (48, 72) (48, 80) (48, 84) (48, 96) (50, 100) (54, 72) (54, 90) (56, 84) (60, 72) (60, 80) (60, 84) (60, 90) (60, 96) (60, 100) (64, 80) (64, 96) (72, 84) (72, 90) (72, 96) (80, 96) (80, 100) (84, 96)\n"
     ]
    }
   ],
   "source": [
    "# List of pairs (i,j) with at least 5 common factors\n",
    "for i in range(1,100):\n",
    "    for j in range(i+1,101):\n",
    "        if num_commonfactors(i,j) >= 5:\n",
    "            print (i,j),"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(c) The size of basket `b` is `floor(100/b)`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "482"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sizeofbaskets = [int(100/b) for b in range(1,101)]\n",
    "totalsize = sum(sizeofbaskets)\n",
    "totalsize"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='exercise-6-1-5'></a>\n",
    "# Exercise 6.1.5\n",
    "For the data of Exercise 6.1.1, what is the confidence of the following association rules?\n",
    "\n",
    "(a) {5,7} -> 2\n",
    "- The support of {5,7} is 2 since {5,7} can be found in baskets (35) and (70). On the other hand, the support of {5,7,2} is 1 since this triple can only be found in basket {70}. Therefore the confidence of this association rule is 1/2.\n",
    "\n",
    "(b) {2,3,4} -> 5\n",
    "- The confidence of this rule is 1/8. Note that basket `b` contains itemset `I` if all of its items are factors of `b`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from __future__ import division"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def supportset_611(I):\n",
    "    sup = []\n",
    "    for b in range(1,101):\n",
    "        # check if all items in I are factors of b\n",
    "        if all(item in factors(b) for item in I):\n",
    "             sup.append(b)\n",
    "    return sup"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[12, 24, 36, 48, 60, 72, 84, 96]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# support set of {2,3,4}\n",
    "supportset_611([2,3,4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[60]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# support set of {2,3,4,5}\n",
    "supportset_611([2,3,4,5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.125"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Confidence of {2,3,4}->5\n",
    "conf_b = len(supportset_611([2,3,4,5]))/len(supportset_611([2,3,4]))\n",
    "conf_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='exercise-6-1-6'></a>\n",
    "# Exercise 6.1.6\n",
    "\n",
    "For the data of Exercise 6.1.3, what is the confidence of the following association rules?\n",
    "\n",
    "(a) {24,60} -> 8\n",
    "- The support of {24,60} is 6 since {24} and {60} share the common factors (1),(2),(3),(4),(6), and (12). The support of {8,24,60} is 3 since only factors (1), (2) and (4) are shared amongst them. Therefore, the confidence of this association rule is 3/6=1/2.\n",
    "\n",
    "(b) {2,3,4} -> 5\n",
    "- The confidence of this association rule is 1. See below"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def supportset_613(I):\n",
    "    \"\"\"\n",
    "    The set of baskets containing itemset I is the set of common\n",
    "    of factors amongst all items in I. This function takes I as\n",
    "    input and outputs the common factors (i.e, the baskets) of \n",
    "    all items contained in I.\n",
    "    \"\"\"\n",
    "    n = len(I)\n",
    "    if n == 1:\n",
    "        return factors(I[0])\n",
    "    elif n == 2:\n",
    "        foo = factors(I[0])\n",
    "        bar = factors(I[1])\n",
    "        return [el for el in foo if el in bar]\n",
    "    else: # use divide and conquer here\n",
    "        half = int(n/2)\n",
    "        firstpart = supportset_613(I[:half])\n",
    "        secondpart = supportset_613(I[half:])\n",
    "        return [el for el in firstpart if el in secondpart]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# support set of {2,3,4} is\n",
    "supportset_613([2,3,4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# support set of {2,3,4,5}\n",
    "supportset_613([2,3,4,5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The confidence of this association rule is 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='exercise-6-2-5'></a>\n",
    "# Exercise 6.2.5\n",
    "\n",
    "Suppose the support threshold is 5. Find the maximal frequent itemsets for the data of:\n",
    "\n",
    "(a) Exercise 6.1.1\n",
    "\n",
    "(b) Exercise 6.1.3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solutions to 6.2.5(a):"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### L1 and L2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#(a)\n",
    "# frequent singletons\n",
    "L1 = range(1,21)\n",
    "L1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# frequent pairs\n",
    "L2 = []\n",
    "for i in range(1,20): # these are the only singletons which are frequent\n",
    "    for j in range(i+1,21):\n",
    "        commonbask = [b for b in baskets[i] if b in baskets[j]]\n",
    "        if len(commonbask) >= 5:\n",
    "            L2.append([i,j])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2] [1, 3] [1, 4] [1, 5] [1, 6] [1, 7] [1, 8] [1, 9] [1, 10] [1, 11] [1, 12] [1, 13] [1, 14] [1, 15] [1, 16] [1, 17] [1, 18] [1, 19] [1, 20] [2, 3] [2, 4] [2, 5] [2, 6] [2, 7] [2, 8] [2, 9] [2, 10] [2, 12] [2, 14] [2, 16] [2, 18] [2, 20] [3, 4] [3, 5] [3, 6] [3, 9] [3, 12] [3, 15] [3, 18] [4, 5] [4, 6] [4, 8] [4, 10] [4, 12] [4, 16] [4, 20] [5, 10] [5, 15] [5, 20] [6, 9] [6, 12] [6, 18] [7, 14] [8, 16] [9, 18] [10, 20]\n"
     ]
    }
   ],
   "source": [
    "for pair in L2:\n",
    "    print pair,"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Maximal singletons "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L2_flatten = []\n",
    "for pair in L2:\n",
    "    L2_flatten += pair\n",
    "    \n",
    "L2_flatten = list(set(L2_flatten))\n",
    "L2_flatten"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Therefore, there are no maximal singletons."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### L3 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# frequent triples\n",
    "L3 = []\n",
    "for i in range(1,21):\n",
    "    for pair in L2:\n",
    "        if i not in pair:\n",
    "            foo = pair+[i]\n",
    "            foo.sort() # works in place\n",
    "            if len(supportset_611(foo)) >= 5 and foo not in L3:\n",
    "                L3.append(foo)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Maximal doubletons "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# check for maximal doubletons\n",
    "maximal_doub = []\n",
    "for pair in L2:\n",
    "    pair_max = False\n",
    "    for trip in L3:\n",
    "        if all(item in trip for item in pair):\n",
    "            pair_max = True\n",
    "            break\n",
    "    if not pair_max:    \n",
    "        maximal_doub.append(pair)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 11], [1, 13], [1, 17], [1, 19]]"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maximal_doub"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### L4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# frequent quads\n",
    "L4 = []\n",
    "for i in range(1,21):\n",
    "    for trip in L3:\n",
    "        if i not in trip:\n",
    "            foo = trip+[i]\n",
    "            foo.sort() # works in place\n",
    "            if len(supportset_611(foo)) >= 5 and foo not in L4:\n",
    "                L4.append(foo)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### maximal triples "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# check for maximal triples\n",
    "maximal_triples = []\n",
    "for trip in L3:\n",
    "    trip_max = False\n",
    "    for quad in L4:\n",
    "        if all(item in quad for item in trip):\n",
    "            trip_max = True\n",
    "            break\n",
    "    if not trip_max:    \n",
    "        maximal_triples.append(trip)\n",
    "maximal_triples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### L5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2, 3, 4, 6],\n",
       " [1, 2, 3, 4, 12],\n",
       " [1, 2, 3, 6, 9],\n",
       " [1, 2, 3, 6, 12],\n",
       " [1, 2, 3, 6, 18],\n",
       " [1, 2, 3, 9, 18],\n",
       " [1, 2, 4, 5, 10],\n",
       " [1, 2, 4, 5, 20],\n",
       " [1, 2, 4, 6, 12],\n",
       " [1, 2, 4, 8, 16],\n",
       " [1, 2, 4, 10, 20],\n",
       " [1, 2, 5, 10, 20],\n",
       " [1, 2, 6, 9, 18],\n",
       " [1, 3, 4, 6, 12],\n",
       " [1, 3, 6, 9, 18],\n",
       " [1, 4, 5, 10, 20],\n",
       " [2, 3, 4, 6, 12],\n",
       " [2, 3, 6, 9, 18],\n",
       " [2, 4, 5, 10, 20]]"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# frequent quintiples\n",
    "L5 = []\n",
    "for i in range(1,21):\n",
    "    for quad in L4:\n",
    "        if i not in quad:\n",
    "            foo = quad+[i]\n",
    "            foo.sort() # works in place\n",
    "            if len(supportset_611(foo)) >= 5 and foo not in L5:\n",
    "                L5.append(foo)\n",
    "L5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Maximal quads "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# check for maximal quads\n",
    "maximal_quads = []\n",
    "for quad in L4:\n",
    "    quad_max = False\n",
    "    for quint in L5:\n",
    "        if all(item in quint for item in quad):\n",
    "            quad_max = True\n",
    "            break\n",
    "    if not quad_max:    \n",
    "        maximal_quads.append(quad)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2, 7, 14], [1, 3, 5, 15]]"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maximal_quads"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[15, 30, 45, 60, 75, 90]"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# looking at one of these\n",
    "supportset_611([1, 3, 5, 15])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### L6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2, 3, 4, 6, 12], [1, 2, 3, 6, 9, 18], [1, 2, 4, 5, 10, 20]]"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# frequent sixtuplets\n",
    "L6 = []\n",
    "for i in range(1,21):\n",
    "    for quint in L5:\n",
    "        if i not in quint:\n",
    "            foo = quint+[i]\n",
    "            foo.sort() # works in place\n",
    "            if len(supportset_611(foo)) >= 5 and foo not in L6:\n",
    "                L6.append(foo)\n",
    "L6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Maximal quintuplets "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# check for maximal quints\n",
    "maximal_quints = []\n",
    "for quint in L5:\n",
    "    quint_max = False\n",
    "    for sixt in L6:\n",
    "        if all(item in sixt for item in quint):\n",
    "            quint_max = True\n",
    "            break\n",
    "    if not quint_max:    \n",
    "        maximal_quints.append(quint)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 2, 4, 8, 16]]"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maximal_quints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### L7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# frequent septuplets\n",
    "L7 = []\n",
    "for i in range(1,21):\n",
    "    for sixt in L6:\n",
    "        if i not in sixt:\n",
    "            foo = sixt+[i]\n",
    "            foo.sort() # works in place\n",
    "            if len(supportset_611(foo)) >= 5 and foo not in L7:\n",
    "                L7.append(foo)\n",
    "L7"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## No septuplets implies that all frequent sixtuplets are maximal!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[12, 24, 36, 48, 60, 72, 84, 96]\n",
      "[18, 36, 54, 72, 90]\n",
      "[20, 40, 60, 80, 100]\n"
     ]
    }
   ],
   "source": [
    "# here are the support sets of each of sixtuplets\n",
    "for sixt in L6:\n",
    "    print supportset_611(sixt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solutions to 6.2.5(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### L1 and L2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12 16 18 20 24 28 30 32 36 40 42 44 45 48 50 52 54 56 60 63 64 66 68 70 72 75 76 78 80 81 84 88 90 92 96 98 99 100\n"
     ]
    }
   ],
   "source": [
    "# List of frequent items\n",
    "L1 = [b for b in range(1,101) if num_factors(b)>=5]\n",
    "\n",
    "for items in L1:\n",
    "    print items,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[12, 24] [12, 36] [12, 48] [12, 60] [12, 72] [12, 84] [12, 96] [16, 32] [16, 48] [16, 64] [16, 80] [16, 96] [18, 36] [18, 54] [18, 72] [18, 90] [20, 40] [20, 60] [20, 80] [20, 100] [24, 36] [24, 48] [24, 60] [24, 72] [24, 84] [24, 96] [28, 56] [28, 84] [30, 60] [30, 90] [32, 48] [32, 64] [32, 80] [32, 96] [36, 48] [36, 54] [36, 60] [36, 72] [36, 84] [36, 90] [36, 96] [40, 60] [40, 80] [40, 100] [42, 84] [44, 88] [45, 90] [48, 60] [48, 64] [48, 72] [48, 80] [48, 84] [48, 96] [50, 100] [54, 72] [54, 90] [56, 84] [60, 72] [60, 80] [60, 84] [60, 90] [60, 96] [60, 100] [64, 80] [64, 96] [72, 84] [72, 90] [72, 96] [80, 96] [80, 100] [84, 96]\n"
     ]
    }
   ],
   "source": [
    "# List of frequent pairs\n",
    "L2 = []\n",
    "for i in range(1,100):\n",
    "    for j in range(i+1,101):\n",
    "        if len(supportset_613([i,j])) >= 5:\n",
    "            L2.append([i,j])\n",
    "\n",
    "for pair in L2:\n",
    "    print pair,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[12, 24] [12, 36] [12, 48] [12, 60] [12, 72] [12, 84] [12, 96] [16, 32] [16, 48] [16, 64] [16, 80] [16, 96] [18, 36] [18, 54] [18, 72] [18, 90] [20, 40] [20, 60] [20, 80] [20, 100] [24, 36] [24, 48] [24, 60] [24, 72] [24, 84] [24, 96] [28, 56] [28, 84] [30, 60] [30, 90] [32, 48] [32, 64] [32, 80] [32, 96] [36, 48] [36, 54] [36, 60] [36, 72] [36, 84] [36, 90] [36, 96] [40, 60] [40, 80] [40, 100] [42, 84] [44, 88] [45, 90] [48, 60] [48, 64] [48, 72] [48, 80] [48, 84] [48, 96] [50, 100] [54, 72] [54, 90] [56, 84] [60, 72] [60, 80] [60, 84] [60, 90] [60, 96] [60, 100] [64, 80] [64, 96] [72, 84] [72, 90] [72, 96] [80, 96] [80, 100] [84, 96]\n"
     ]
    }
   ],
   "source": [
    "# List of frequent pairs\n",
    "L2 = []\n",
    "for i in range(1,100):\n",
    "    for j in range(i+1,101):\n",
    "        if num_commonfactors(i,j) >= 5:\n",
    "            L2.append([i,j])\n",
    "\n",
    "for pair in L2:\n",
    "    print pair,"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Maximal singletons"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[52, 63, 66, 68, 70, 75, 76, 78, 81, 92, 98, 99]"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# check for maximal singletons\n",
    "maximal_single = []\n",
    "for single in L1:\n",
    "    single_max = False\n",
    "    for pair in L2:\n",
    "        if all(item in pair for item in [single]):\n",
    "            single_max = True\n",
    "            break\n",
    "    if not single_max:    \n",
    "        maximal_single.append(single)\n",
    "maximal_single"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### L3 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# List of frequent triples\n",
    "L3 = []\n",
    "for single in L1:\n",
    "    for pair in L2:\n",
    "        if single not in pair:\n",
    "            foo = pair+[i]\n",
    "            foo.sort() # works in place\n",
    "            if len(supportset_613(foo)) >= 5 and foo not in L3:\n",
    "                L3.append(foo)\n",
    "L3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### No frequent triples, means that every doubleton is maximal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='exercise-6-2-6'></a>\n",
    "# Exercise 6.2.6 (A-Priori Algorithm) \n",
    "\n",
    "Apply the A-Priori Algorithm with support threshold 5 to the data of:\n",
    "\n",
    "(a) Exercise 6.1.1.\n",
    "\n",
    "(b) Exercise 6.1.3.\n",
    "\n",
    "To make this more interesting, let's map integers `i` to strings using english stopwords."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# generate the baskets: basket b consists of all items i that are factors of b\n",
    "baskets_611 = {}\n",
    "for i in range(1,101):\n",
    "    baskets_611[i] = factors(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Converting numeric baskets to corresponding words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 296,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# print a file containing baskets enclosed by curly braces {}\n",
    "baskets_611_words = []\n",
    "for i in range(1,101):\n",
    "     baskets_611_words.append([','.join([words[int] for int in baskets_611[i]])])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solution to 6.2.6(a) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## First pass of A-Priori\n",
    "\n",
    "In the first pass, we count the frequency of singletons as we read the baskets and store these into an array. Clearly do not need to map items into integers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "C1 = {i:0 for i in range(1,101)}\n",
    "for b in baskets_611.values():\n",
    "    for i in b:\n",
    "        C1[i] += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Between the Passes of A-Priori\n",
    "\n",
    "Generate the list of singletons that are frequent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# support threshold\n",
    "s = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "L1 = [item for item,count in C1.items() if count >= s]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Second Pass of A-Priori\n",
    "\n",
    "1. For each basket, look in the frequent-items table to see which of its items are frequent.\n",
    "\n",
    "2. In a double loop, generate all pairs of frequent items in that basket.\n",
    "\n",
    "3. For each such pair, add one to its count in the data structure used to store counts."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using triangular-matrix method to store counts of pairs:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def triangularmatrix_method(i,j,n):\n",
    "    \"\"\"\n",
    "    returns the index for the triangular matrix method \n",
    "    A[i,j] = a[k] in a flattened array... 1<=i<j<=n\n",
    "    \"\"\"\n",
    "    return int((i-1)*(n-i/2)) + j-i - 1 # minus one at end for Python arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 216,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# initialize the flattened array for triangular matrix\n",
    "m = len(L1)\n",
    "C2 = [0]*int(m*(m-1)/2)\n",
    "\n",
    "# second pass of the baskets\n",
    "# using a triangular-matrix for counting\n",
    "for b in baskets_611.values():\n",
    "    freq_items = [item for item in b if item in L1]\n",
    "    # in a double loop, generate all pairs of frequent items in that basket\n",
    "    for ix in range(len(freq_items)-1):\n",
    "        for jx in range(ix+1,len(freq_items)):\n",
    "            i = min(freq_items[ix],freq_items[jx])\n",
    "            j = max(freq_items[ix],freq_items[jx])\n",
    "            C2[triangularmatrix_method(i,j,m)] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 217,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# extracting frequent pair indices from C2\n",
    "pair_indices = [i for i,cnt in enumerate(C2) if cnt >= s]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 218,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "56"
      ]
     },
     "execution_count": 218,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(pair_indices)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 219,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 28 30 32 34 36 37 38 39 42 45 48 51 54 55 57 59 61 65 69 74 79 84 87 90 96 105 119 132 144\n"
     ]
    }
   ],
   "source": [
    "# k values we need to inverse map to get pair (i,j)\n",
    "for ix in pair_indices:\n",
    "    print ix,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 220,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# grabbing pairs (i,j) from flattened array\n",
    "def inv_triangle(ix,n):\n",
    "    init = n-1\n",
    "    i = 1\n",
    "    while ix > init:\n",
    "        i += 1\n",
    "        init += n-i\n",
    "    # decrement init back once\n",
    "    init -= n-i\n",
    "    return [i,i+ix-init]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 221,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# have to add one in argument because Python arrays start at index 0\n",
    "L2 = [inv_triangle(ix+1,m) for ix in pair_indices]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 222,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2] [1, 3] [1, 4] [1, 5] [1, 6] [1, 7] [1, 8] [1, 9] [1, 10] [1, 11] [1, 12] [1, 13] [1, 14] [1, 15] [1, 16] [1, 17] [1, 18] [1, 19] [1, 20] [2, 3] [2, 4] [2, 5] [2, 6] [2, 7] [2, 8] [2, 9] [2, 10] [2, 12] [2, 14] [2, 16] [2, 18] [2, 20] [3, 4] [3, 5] [3, 6] [3, 9] [3, 12] [3, 15] [3, 18] [4, 5] [4, 6] [4, 8] [4, 10] [4, 12] [4, 16] [4, 20] [5, 10] [5, 15] [5, 20] [6, 9] [6, 12] [6, 18] [7, 14] [8, 16] [9, 18] [10, 20]\n"
     ]
    }
   ],
   "source": [
    "# frequent pairs is thus:\n",
    "for pair in L2:\n",
    "    print pair,"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}