0307_notebook.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "s={1,4,3,3,2}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1, 2, 3, 4}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "s.add('four')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1, 2, 3, 4, 'four'}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "3 in s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1, 2, 3, 4, 5, 6, 7, 'four'}"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.union({4,5,6,7})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1, 2, 3}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.intersection({1,2,3})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing my own list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Link:\n",
    "    empty=()\n",
    "    \n",
    "    def __init__(self,first,rest=empty):\n",
    "        assert rest is Link.empty or isinstance(rest,Link)\n",
    "        self.first = first\n",
    "        self.rest = rest\n",
    "        \n",
    "    def __repr__(self):\n",
    "        if self.rest:\n",
    "            rest_str = ', ' + repr(self.rest)\n",
    "        else:\n",
    "            rest_str = ''\n",
    "        return 'Link({0}{1})'.format(self.first,rest_str)\n",
    "    \n",
    "    def __str__(self):\n",
    "        string = '<'\n",
    "        while self.rest is not Link.empty:\n",
    "            string +=str(self.first) + ', '\n",
    "            self = self.rest\n",
    "        return string+str(self.first)+'>'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Sets as sorted sequences"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def empty(s):\n",
    "    return s is Link.empty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def contains(s,v):\n",
    "    \"\"\"Return True if s contains value v as an element\"\"\"\n",
    "    if empty(s):\n",
    "        return False\n",
    "    elif v == s.first:\n",
    "        return True\n",
    "    else:\n",
    "        return contains(s.rest,v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "s = Link(1,Link(2,Link(3)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "contains(s,6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def adjoin(s,v):\n",
    "    \"\"\"Return a set containing all elements of s and element v\"\"\"\n",
    "    if contains(s,v):\n",
    "        return s\n",
    "    else:\n",
    "        return Link(v,s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "def intersect(s,t):\n",
    "    \"\"\"Return a set containing all elements common to s and t\"\"\"\n",
    "    if empty(s):\n",
    "        return s\n",
    "    rest = intersect(s.rest,t)\n",
    "    if contains(t,s.first):\n",
    "        return Link(s.first,rest)\n",
    "    else:\n",
    "        return rest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def union(s,t):\n",
    "    \"\"\"Return a set containing all elements either in s or t\"\"\"\n",
    "    if empty(s):\n",
    "        return t\n",
    "    rest = union(s.rest,t)\n",
    "    if contains(t,s.first):\n",
    "        return rest\n",
    "    else:\n",
    "        return Link(s.first,rest)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Sets as (sorted) ordered sequences,我们自己假设set是有序的"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def contains2(s,v):\n",
    "    \"\"\"Return true if set s contains value v as an element.\"\"\"\n",
    "    if empty(s):\n",
    "        return False\n",
    "    elif v<s.first:\n",
    "        return False\n",
    "    return contains(s.rest,v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def adjoin2(s,v):\n",
    "    \"\"\"Return a set containing all elements of s and element v.\"\"\"\n",
    "    if empty(s) or v<s.first:\n",
    "        return Link(v,s)\n",
    "    elif v == s.first:\n",
    "        return s\n",
    "    else:\n",
    "        return Link(s.first,adjoin2(s.rest,v))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def add(s,v):\n",
    "    \"\"\"Add v to a set s, returning modified s. If s is not empty,\n",
    "    returns same object.\"\"\"\n",
    "    if empty(s):\n",
    "        return Link(v)\n",
    "    if s.first > v:\n",
    "        s.first,s.rest = v, Link(s.first,s.rest)\n",
    "    elif s.first < v and empty(s.rest):\n",
    "        s.rest = Link(v)\n",
    "    elif s.first < v:\n",
    "        add(s.rest,v)\n",
    "    return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def intersect2(s,t):\n",
    "    \"\"\"Return a set containing all elements common to s and t.\"\"\"\n",
    "    if empty(s) or empty(t):\n",
    "        return Link.empty\n",
    "    else:\n",
    "        e1,e2 = s.first,t.first\n",
    "        if e1==e2:\n",
    "            return Link(e1,intersect2(s.rest,t.rest))\n",
    "        elif e1<e2:\n",
    "            return intersect2(s.rest,t)\n",
    "        elif e2<e1:\n",
    "            return intersect2(s,t.rest)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def union2(s,t):\n",
    "    \"\"\"Return a set containing all elements either in s or t.\"\"\"\n",
    "    if empty(s):\n",
    "        return t\n",
    "    elif empty(t):\n",
    "        return s\n",
    "    else:\n",
    "        e1,e2 = s.first,t.first\n",
    "        if e1==e2:\n",
    "            return Link(e1,union2(s.rest,t.rest))\n",
    "        elif e1<e2:\n",
    "            return Link(e1,union2(s.rest,t))\n",
    "        else:\n",
    "            return Link(e2,union2(s,t.rest))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sum_nums(lnk):\n",
    "    sum=0\n",
    "    while lnk is not Link.empty:\n",
    "        sum+=lnk.first\n",
    "        lnk = lnk.rest\n",
    "    return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Link(0, Link(1, Link(2, Link(3, Link(5, Link(6))))))"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "17"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum_nums(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sum_nums(lnk):\n",
    "    if lnk is Link.empty:\n",
    "        return 0\n",
    "    else:\n",
    "        return lnk.first + sum_nums(lnk.rest)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [],
   "source": [
    "def multiply_lnks(lst_of_lnks):\n",
    "    \"\"\"\n",
    "    >>> a = Link(2, Link(3, Link(5)))\n",
    "    >>> b = Link(6, Link(4, Link(2)))\n",
    "    >>> c = Link(4, Link(1, Link(0, Link(2))))\n",
    "    >>> p = multiply_lnks([a, b, c])\n",
    "    >>> p.first\n",
    "    48\n",
    "    >>> p.rest.first\n",
    "    12\n",
    "    >>> p.rest.rest.rest\n",
    "    ()\n",
    "    \"\"\"\n",
    "    pro = 1\n",
    "    for lnk in lst_of_lnks:\n",
    "        if empty(lnk):\n",
    "            return Link.empty\n",
    "        pro*=lnk.first\n",
    "    link_rest = [lnk.rest for lnk in lst_of_lnks]\n",
    "    return Link(pro,multiply_lnks(link_rest))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "48"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = Link(2, Link(3, Link(5)))\n",
    "b = Link(6, Link(4, Link(2)))\n",
    "c = Link(4, Link(1, Link(0, Link(2))))\n",
    "p = multiply_lnks([a, b, c])\n",
    "p.first"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p.rest.first"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "()"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p.rest.rest.rest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def remove_duplicates(lnk):\n",
    "    if empty(lnk):\n",
    "        return Link.empty\n",
    "    else:\n",
    "        v=lnk.first\n",
    "        while lnk.rest is not Link.empty and v == lnk.rest.first:\n",
    "            lnk.rest = lnk.rest.rest\n",
    "        return Link(v,lnk.rest)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "l = Link(1,Link(1,Link(1,Link(2,Link(3)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [],
   "source": [
    "m=remove_duplicates(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Link(1, Link(2, Link(3)))"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Link(1, Link(2, Link(3)))"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 8]"
      ]
     },
     "execution_count": 106,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[i*x for i,x in enumerate([2,5,4]) if i%2==0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def quicksort_list(lst):\n",
    "    if len(lst)<2:\n",
    "        return lst\n",
    "    pivot=lst[0]\n",
    "    less = [x for x in lst[1:] if x<pivot]\n",
    "    greater = [x for x in lst[1:] if x>pivot]\n",
    "    return quicksort_list(less) + [pivot] + quicksort_list(greater)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 8, 9]"
      ]
     },
     "execution_count": 119,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "quicksort_list([1,4,2,3,8,5,9,6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def max_product(lst):\n",
    "    if lst == []:\n",
    "        return 1\n",
    "    elif len(lst) ==1:\n",
    "        return lst[0]\n",
    "    else:\n",
    "        return max(max_product(lst[1:]),lst[0]*max_product(lst[2:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "90"
      ]
     },
     "execution_count": 129,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max_product([10,3,1,9,2])"
   ]
  }
 ],
 "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}