{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [], "source": [ "import itertools\n", "\n", "def overlap(a, b, min_length=3):\n", " \"\"\" Return length of longest suffix of 'a' matching\n", " a prefix of 'b' that is at least 'min_length'\n", " characters long. If no such overlap exists,\n", " return 0. \"\"\"\n", " start = 0 # start all the way at the left\n", " while True:\n", " start = a.find(b[:min_length], start) # look for b's suffx in a\n", " if start == -1: # no more occurrences to right\n", " return 0\n", " # found occurrence; check for full suffix/prefix match\n", " if b.startswith(a[start:]):\n", " return len(a)-start\n", " start += 1 # move just past previous match\n", "\n", "def scs(ss):\n", " \"\"\" Returns shortest common superstring of given\n", " strings, which must be the same length \"\"\"\n", " shortest_sup = None\n", " for ssperm in itertools.permutations(ss):\n", " sup = ssperm[0] # superstring starts as first string\n", " for i in range(len(ss)-1):\n", " # overlap adjacent strings A and B in the permutation\n", " olen = overlap(ssperm[i], ssperm[i+1], min_length=1)\n", " # add non-overlapping portion of B to superstring\n", " sup += ssperm[i+1][olen:]\n", " if shortest_sup is None or len(sup) < len(shortest_sup):\n", " shortest_sup = sup # found shorter superstring\n", " return shortest_sup # return shortest" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "'BAAABABBBA'" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "scs(['BAA', 'AAB', 'BBA', 'ABA', 'ABB', 'BBB', 'AAA', 'BAB'])" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "'ABCDBCDA'" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "scs(['ABCD', 'CDBC', 'BCDA'])" ] } ], "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.10" } }, "nbformat": 4, "nbformat_minor": 0 }