longest_increasing_subsequence.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Longest Increasing Subsequence\n",
    "\n",
    "**Given:** a positive integer $n$ followed by a permuted vector ($\\pi$) of length $n$\n",
    "\n",
    "**Return:** The longest increasing subsequence of $\\pi$, followed by the longest decreasing subsequence of $\\pi$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Slow method\n",
    "\n",
    "1. start as $i =$  length($\\pi$)\n",
    "2. find all subsequences of $\\pi$ with length of $i$\n",
    "3. if there is an increasing subsequence, return that\n",
    "4. else, decrease $i$ by 1\n",
    "\n",
    "**Time taken takes exponentially longer as length of sequence increases $O(n^2)$ **"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from __future__ import print_function\n",
    "from itertools import combinations\n",
    "\n",
    "def is_incr(x):\n",
    "    x = list(x)\n",
    "    if sorted(x) == x:\n",
    "        return True\n",
    "    \n",
    "def is_decr(x):\n",
    "    x = list(x)\n",
    "    if sorted(x, reverse = True) == x:\n",
    "        return True\n",
    "\n",
    "def longest(x, direction):\n",
    "    \n",
    "    if direction == \"increasing\": \n",
    "        direc = is_incr\n",
    "    elif direction == \"decreasing\":\n",
    "        direc = is_decr\n",
    "    else:\n",
    "        raise ValueError(\"you idiot\")\n",
    "        \n",
    "    for i in range(len(x), 0, -1): # decreasing\n",
    "        subs = combinations(x, i)\n",
    "        for s in subs:\n",
    "            if direc(s):\n",
    "                return s\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 6 7 9\n",
      "8 6 5 4 3\n"
     ]
    }
   ],
   "source": [
    "# test data\n",
    "n = 9\n",
    "pi = [8, 2, 1, 6, 5, 7, 4, 3, 9]\n",
    "\n",
    "print(*longest(pi, \"increasing\"))\n",
    "print(*longest(pi, \"decreasing\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quicker method\n",
    "\n",
    "First method is slow as balls - *just* runs within the 5 minute time limit for the real data if I run both as separate processes.\n",
    "\n",
    "### [Binary search](https://en.wikipedia.org/wiki/Binary_search_algorithm)\n",
    "\n",
    "Uses a sorted array, tests if a value is equal to the middle of an array.  \n",
    "If the value is > than the middle, repeats the operation in the second half of the array.  \n",
    "If the value is < than middle of the array, repeats operation in first half of the array.  \n",
    "Repeat until value is equal to middle.\n",
    "\n",
    "Can use the sorted array and then reference indices back to $\\pi$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import operator\n",
    "# so I can have a variable set to '>' or '<'\n",
    "# as the difference between increasing and decreasing methods is a single operator\n",
    "\n",
    "def get_vals(path):\n",
    "    \"get values from file (skipping first number)\"\n",
    "    return map(int, open(path).read().split(' ')[1:])\n",
    "\n",
    "def set_direction(direction):\n",
    "    \"return operator as variable depending on input for `direction\"\n",
    "    if direction == \"increasing\": \n",
    "        direc = operator.lt # less than\n",
    "    elif direction == \"decreasing\":\n",
    "        direc = operator.gt # greater than\n",
    "    else:\n",
    "        raise ValueError(\"invalid direction\")\n",
    "    return direc\n",
    "\n",
    "\n",
    "\n",
    "def longest(path, direction):\n",
    "    \"\"\"\n",
    "    path: file path to rosalind_lgis.txt\n",
    "    direction: increasing or decreasing subsequence\n",
    "    \"\"\"\n",
    "    pi = get_vals(path)\n",
    "    direc = set_direction(direction)\n",
    "    P = [None] * len(pi)\n",
    "    M = [0]\n",
    "    \n",
    "    for i in range(1, len(pi)):\n",
    "        low = 0\n",
    "        high = len(M)\n",
    "        while low < high:\n",
    "            # set mid to actual middle\n",
    "            mid = int((low + high) / 2) \n",
    "            if direc(pi[M[mid]], pi[i]): # if pi[M[mid]] '<'/'>' pi[i]\n",
    "                # shift to second half of array\n",
    "                low = mid + 1 \n",
    "            else:\n",
    "                # halve the first half of the array\n",
    "                high = mid \n",
    "        if low > 0:\n",
    "            P[i] = M[low - 1]\n",
    "        if low > len(M) - 1:\n",
    "            M.append(i)\n",
    "        else:\n",
    "            M[low] = i\n",
    "    S = []\n",
    "    k = M[-1]\n",
    "    n = len(M)\n",
    "    \n",
    "    # probably a better way to do this\n",
    "    while n > 0:\n",
    "        S.append(pi[k])\n",
    "        k = P[k]\n",
    "        n -= 1\n",
    "    return S[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "149 185 278 285 294 299 315 317 358 369 418 429 530 572 576 612 623 657 660 669 728 802 803 822 838 846 852 980 1042 1080 1124 1196 1295 1320 1357 1359 1375 1479 1497 1572 1580 1603 1653 1668 1677 1744 1819 1849 1858 1894 1911 1991 2063 2086 2142 2144 2148 2285 2313 2431 2472 2514 2738 2757 2775 2862 3039 3043 3104 3189 3249 3294 3311 3387 3424 3477 3501 3607 3651 3688 3736 3771 3856 3865 3882 3944 3971 4040 4079 4111 4245 4388 4452 4527 4537 4544 4598 4607 4623 4625 4654 4690 4702 4718 4731 4774 4847 4901 4933 4974 4991 5004 5078 5261 5296 5333 5336 5338 5372 5419 5480 5513 5530 5555 5656 5657 5751 5790 5860 5873 5897 5930 5958 6011 6065 6135 6149 6155 6213 6218 6281 6315 6499 6526 6593 6615 6698 6795 6836 6874 6904 6973 7011 7086 7094 7149 7202 7243 7268 7309 7314 7349 7350 7395 7455 7463 7581 7583 7702 7838 7846 7867 7889 7926 7945 7981 8012 8045 8083 8109\n",
      "\n",
      "\n",
      "8135 8110 8104 7768 7716 7401 6970 6932 6866 6859 6826 6823 6773 6580 6511 6269 6207 6148 6043 6026 5996 5938 5934 5903 5894 5792 5748 5684 5669 5642 5637 5577 5562 5556 5520 5439 5381 5334 5295 5275 5260 5230 5216 5206 5174 5086 5038 5002 4934 4910 4871 4856 4658 4611 4609 4556 4554 4553 4482 4468 4442 4429 4355 4336 4251 4202 4034 3884 3868 3842 3813 3811 3739 3718 3615 3581 3425 3392 3307 3194 3185 3136 3057 2924 2917 2873 2852 2843 2799 2792 2731 2673 2514 2489 2454 2438 2366 2331 2243 2225 2204 2199 2093 2079 2027 2014 2003 2001 1999 1952 1936 1903 1850 1831 1816 1770 1755 1719 1689 1686 1669 1641 1607 1578 1555 1549 1540 1521 1419 1356 1344 1338 1327 1294 1219 1209 1208 1139 1030 1013 920 896 881 869 867 851 840 813 798 774 760 753 583 574 521 515 488 481 461 457 447 381 262 203 129 98\n"
     ]
    }
   ],
   "source": [
    "path = \"/home/scott/Dropbox/rosalind/rosalind_lgis.txt\"\n",
    "print(*longest(path, \"increasing\"))\n",
    "print(\"\\n\")\n",
    "print(*longest(path, \"decreasing\"))"
   ]
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}