Dynamic Programming.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## DPV 6.7: Longest Palindromic Subsequence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "X = list(\"RXCABACYR\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 350,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_longest_palindromic_subsequence(X):\n",
    "    \n",
    "    n = len(X)\n",
    "    L = np.zeros((n, n))\n",
    "    \n",
    "    for i in range(n):\n",
    "        L[i, i] = 1 \n",
    "    for i in range(n-1):\n",
    "        L[i, i+1] = 2\n",
    "        \n",
    "    for w in range(2, n):\n",
    "        for i in range(0, n-w):\n",
    "            j = i + w\n",
    "            #print(w, i, j)\n",
    "            if X[i] == X[j]:\n",
    "                L[i, j] = L[i+1, j-1] + 2\n",
    "            else:\n",
    "                L[i, j] = max(L[i, j-1], L[i+1, j])\n",
    "    return L[0,n-1], L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 351,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7.0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([[ 1.,  2.,  2.,  2.,  2.,  3.,  5.,  5.,  7.],\n",
       "       [ 0.,  1.,  2.,  2.,  2.,  3.,  5.,  5.,  5.],\n",
       "       [ 0.,  0.,  1.,  2.,  2.,  3.,  5.,  5.,  5.],\n",
       "       [ 0.,  0.,  0.,  1.,  2.,  3.,  3.,  3.,  3.],\n",
       "       [ 0.,  0.,  0.,  0.,  1.,  2.,  2.,  2.,  2.],\n",
       "       [ 0.,  0.,  0.,  0.,  0.,  1.,  2.,  2.,  2.],\n",
       "       [ 0.,  0.,  0.,  0.,  0.,  0.,  1.,  2.,  2.],\n",
       "       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.,  2.],\n",
       "       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.]])"
      ]
     },
     "execution_count": 351,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length, L = find_longest_palindromic_subsequence(X)\n",
    "print(length)\n",
    "L"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## DPV 6.7 variant: Longest Palindromic Substring"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 360,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_longest_palindromic_sbustring(X):\n",
    "    \n",
    "    n = len(X)\n",
    "    L = np.zeros((n, n))\n",
    "    \n",
    "    for i in range(n):\n",
    "        L[i, i] = 1 \n",
    "    for i in range(n-1):\n",
    "        L[i, i+1] = 2\n",
    "        \n",
    "    for w in range(2, n):\n",
    "        for i in range(0, n-w):\n",
    "            j = i + w\n",
    "            #print(w, i, j)\n",
    "            if X[i] == X[j]:\n",
    "                L[i, j] = L[i+1, j-1] + 2\n",
    "            else:\n",
    "                L[i, j] = 0\n",
    "    return np.max(L), L # <- Notice max here, as we are not doing max inside to avoid subsequence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 361,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5.0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([[ 1.,  2.,  0.,  0.,  0.,  0.,  0.,  0.,  2.],\n",
       "       [ 0.,  1.,  2.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 0.,  0.,  1.,  2.,  0.,  0.,  5.,  0.,  0.],\n",
       "       [ 0.,  0.,  0.,  1.,  2.,  3.,  0.,  0.,  0.],\n",
       "       [ 0.,  0.,  0.,  0.,  1.,  2.,  0.,  0.,  0.],\n",
       "       [ 0.,  0.,  0.,  0.,  0.,  1.,  2.,  0.,  0.],\n",
       "       [ 0.,  0.,  0.,  0.,  0.,  0.,  1.,  2.,  0.],\n",
       "       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.,  2.],\n",
       "       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.]])"
      ]
     },
     "execution_count": 361,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length, L = find_longest_palindromic_sbustring(X)\n",
    "print(length)\n",
    "L"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Longest Increasing Subsequence "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 5, 13,  9, 19,  4, 18,  9,  7,  7, 10,  2, 14, 11,  7, 10,  3, 19,\n",
       "       12, 14, 14])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X = np.random.randint(0,20,20)\n",
    "X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def LIS(X):\n",
    "    \n",
    "    n = len(X)\n",
    "    L = np.zeros(n)\n",
    "    parent = [None for l in L]\n",
    "    \n",
    "    for j in range(n):\n",
    "        L[j] = 1\n",
    "        for i in range(0,j-1):\n",
    "            if X[i] < X[j] and 1 + L[i] > L[j]:\n",
    "                L[j] = 1 + L[i]\n",
    "                parent[j] = i\n",
    "                \n",
    "    return L, parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_LIS(X, L, parent):\n",
    "    \n",
    "    idx = np.argmax(L)\n",
    "    S = [X[idx]]\n",
    "    while parent[idx]:\n",
    "        S.append(X[parent[idx]])\n",
    "        idx = parent[idx]\n",
    "        \n",
    "    S.append(X[parent[idx]])\n",
    "    return S[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 1.  1.  2.  2.  1.  3.  2.  2.  2.  3.  1.  4.  4.  2.  3.  2.  5.  5.\n",
      "  5.  6.]\n",
      "[None, None, 0, 0, None, 2, 0, 0, 0, 2, None, 9, 9, 0, 2, 10, 11, 12, 12, 17]\n"
     ]
    }
   ],
   "source": [
    "L, parent = LIS(X)\n",
    "print L\n",
    "print parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 5, 13,  9, 19,  4, 18,  9,  7,  7, 10,  2, 14, 11,  7, 10,  3, 19,\n",
       "       12, 14, 14])"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 9, 10, 11, 12, 14]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print_LIS(X, L, parent)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Longest Common Subsequence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['B', 'D', 'C', 'A', 'D', 'A', 'A', 'D', 'B', 'C']\n",
      "['B', 'A', 'E', 'D', 'B', 'A', 'B', 'B', 'E', 'D']\n"
     ]
    }
   ],
   "source": [
    "X = [chr(np.random.randint(65, 65+5)) for i in range(10)]\n",
    "Y = [chr(np.random.randint(65, 65+5)) for i in range(10)]\n",
    "print X\n",
    "print Y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [],
   "source": [
    "def LCS(X, Y):\n",
    "    \n",
    "    n, m = len(X), len(Y)\n",
    "    L = np.zeros((n,m))\n",
    "    \n",
    "    for i in range(n):\n",
    "        L[i, 0] = 0\n",
    "    for j in range(m):\n",
    "        L[0, j] = 0\n",
    "    \n",
    "    for i in range(1,n):\n",
    "        for j in range(1,m):\n",
    "            if X[i] == Y[j]:\n",
    "                L[i, j] = 1 + L[i-1, j-1] # max(1 + L[i-1, j-1], L[i-1, j], L[i, j-1]) \n",
    "            else:\n",
    "                L[i, j] = max(L[i-1, j], L[i, j-1])\n",
    "    return L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],\n",
       "       [ 0.,  0.,  0.,  1.,  1.,  1.,  1.,  1.,  1.,  1.],\n",
       "       [ 0.,  0.,  0.,  1.,  1.,  1.,  1.,  1.,  1.,  1.],\n",
       "       [ 0.,  1.,  1.,  1.,  1.,  2.,  2.,  2.,  2.,  2.],\n",
       "       [ 0.,  1.,  1.,  2.,  2.,  2.,  2.,  2.,  2.,  3.],\n",
       "       [ 0.,  1.,  1.,  2.,  2.,  3.,  3.,  3.,  3.,  3.],\n",
       "       [ 0.,  1.,  1.,  2.,  2.,  3.,  3.,  3.,  3.,  3.],\n",
       "       [ 0.,  1.,  1.,  2.,  2.,  3.,  3.,  3.,  3.,  4.],\n",
       "       [ 0.,  1.,  1.,  2.,  3.,  3.,  4.,  4.,  4.,  4.],\n",
       "       [ 0.,  1.,  1.,  2.,  3.,  3.,  4.,  4.,  4.,  4.]])"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L = LCS(X, Y)\n",
    "L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Print_LCS(X, Y, L, i, j):\n",
    "    \n",
    "    \n",
    "    if L[i, j] == 0:\n",
    "        return\n",
    "    \n",
    "    if X[i] == Y[j]:\n",
    "        Print_LCS(X, Y, L, i-1, j-1)\n",
    "        print X[i],\n",
    "        return\n",
    "    else:\n",
    "        if L[i, j] == L[i, j-1]:\n",
    "            Print_LCS(X, Y, L, i, j-1)\n",
    "        elif L[i, j] == L[i-1, j]:\n",
    "            Print_LCS(X, Y, L, i-1, j)\n",
    "        return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A D A B\n"
     ]
    }
   ],
   "source": [
    "Print_LCS(X, Y, L, len(X)-1, len(Y)-1)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "littman_rl_exp",
   "language": "python",
   "name": "littman_rl_exp"
  },
  "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}