Created
November 17, 2015 18:45
-
-
Save gjhernandezp/921e402d0ba22c665ed0 to your computer and use it in GitHub Desktop.
lcs
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"cells": [ | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"Modified from http://rosettacode.org/wiki/Longest_common_subsequence#Python" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 1, | |
"metadata": { | |
"collapsed": true | |
}, | |
"outputs": [], | |
"source": [ | |
"def lcsRF(xstr, ystr):\n", | |
" if not xstr or not ystr:\n", | |
" return \"\"\n", | |
" x, xs, y, ys = xstr[0], xstr[1:], ystr[0], ystr[1:]\n", | |
" if x == y:\n", | |
" return x + lcsRF(xs, ys)\n", | |
" else:\n", | |
" return max(lcsRF(xstr, ys), lcsRF(xs, ystr), key=len)" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 2, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": [ | |
"'tsitest'" | |
] | |
}, | |
"execution_count": 2, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
], | |
"source": [ | |
"lcsRF('thisisatest', 'testing123testing')" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 3, | |
"metadata": { | |
"collapsed": true | |
}, | |
"outputs": [], | |
"source": [ | |
"def lcsRB(xstr, ystr):\n", | |
" if not xstr or not ystr:\n", | |
" return \"\"\n", | |
" x, xs, y, ys = xstr[len(xstr)-1], xstr[:len(xstr)-1], ystr[len(ystr)-1], ystr[:len(ystr)-1]\n", | |
" if x == y:\n", | |
" return lcsRB(xs, ys) + x \n", | |
" else:\n", | |
" return max(lcsRB(xstr, ys), lcsRB(xs, ystr), key=len)" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 4, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": [ | |
"'tsitest'" | |
] | |
}, | |
"execution_count": 4, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
], | |
"source": [ | |
"lcsRB('thisisatest', 'testing123testing')" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 5, | |
"metadata": { | |
"collapsed": true | |
}, | |
"outputs": [], | |
"source": [ | |
"def lcsDP(a, b):\n", | |
" lengths = [[0 for j in range(len(b)+1)] for i in range(len(a)+1)]\n", | |
" # row 0 and column 0 are initialized to 0 already\n", | |
" for i, x in enumerate(a):\n", | |
" for j, y in enumerate(b):\n", | |
" if x == y:\n", | |
" lengths[i+1][j+1] = lengths[i][j] + 1\n", | |
" else:\n", | |
" lengths[i+1][j+1] = \\\n", | |
" max(lengths[i+1][j], lengths[i][j+1])\n", | |
" # read one the substring out from the matrix\n", | |
" result = \"\"\n", | |
" x, y = len(a), len(b)\n", | |
" while x != 0 and y != 0:\n", | |
" if lengths[x][y] == lengths[x-1][y]:\n", | |
" x -= 1\n", | |
" elif lengths[x][y] == lengths[x][y-1]:\n", | |
" y -= 1\n", | |
" else:\n", | |
" assert a[x-1] == b[y-1]\n", | |
" result = a[x-1] + result\n", | |
" x -= 1\n", | |
" y -= 1\n", | |
" return result" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 6, | |
"metadata": { | |
"collapsed": false | |
}, | |
"outputs": [ | |
{ | |
"data": { | |
"text/plain": [ | |
"'tsitest'" | |
] | |
}, | |
"execution_count": 6, | |
"metadata": {}, | |
"output_type": "execute_result" | |
} | |
], | |
"source": [ | |
"lcsDP('thisisatest', 'testing123testing')" | |
] | |
} | |
], | |
"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.4.3" | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 0 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment