+ "execution_count": 21,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def is_interleave_rows(seq1, seq2, seq3, return_backpointers=False, debug=False):\n",
+ " \"\"\"Return true if seq3 is some interleaved merge of seq1 and seq2.\n",
+ " If return_backpointers, also return the set of backpointers to\n",
+ " reconstruct the interleaving.\n",
+ " \n",
+ " This version doesn't build the whole table, just keeps the current and previous rows\"\"\"\n",
+ " \n",
+ " # dp_table[i, j] is True if first i+j characters of seq is made up of \n",
+ " # an interleaving of the first i characters of seq1 and the \n",
+ " # first j characters of seq2\n",
+ " \n",
+ " if len(seq1) + len(seq2) != len(seq3):\n",
+ " if return_backpointers:\n",
+ " retval = [False]\n",
+ " if return_backpointers:\n",
+ " retval += [{}]\n",
+ " return tuple(retval)\n",
+ " else:\n",
+ " return False\n",
+ " \n",
+ "\n",
+ " backpointers = {}\n",
+ "\n",
+ " for i in range(len(seq1)+1):\n",
+ " row = [False] * (len(seq2)+1)\n",
+ " for j in range(len(seq2)+1):\n",
+ " if i == 0 and j == 0:\n",
+ " row[j] = True\n",
+ " if debug: print('xxxx', i, j, '!', '!', '!', row[j])\n",
+ " elif i == 0:\n",
+ " # extend by character from seq2\n",
+ " if row[j-1] and seq2[j-1] == seq3[i+j-1]:\n",
+ " row[j] = True\n",
+ " backpointers[i, j] = (i, j-1, seq2[j-1], 'seq2')\n",
+ " if debug: print('seq2', i, j, '!', seq2[j-1], seq3[i+j-1], row[j])\n",
+ " elif j == 0:\n",
+ " # extend by character from seq1\n",
+ " if previous_row[j] and seq1[i-1] == seq3[i+j-1]:\n",
+ " row[j] = True\n",
+ " backpointers[i, j] = (i-1, j, seq1[i-1], 'seq1')\n",
+ " if debug: print('seq1', i, j, seq1[i-1], '!', seq3[i+j-1], row[j])\n",
+ " else:\n",
+ " # extend by character from seq2\n",
+ " if row[j-1] and seq2[j-1] == seq3[i+j-1]:\n",
+ " row[j] = True\n",
+ " backpointers[i, j] = (i, j-1, seq2[j-1], 'seq2')\n",
+ " if debug: print('seq2', i, j, seq1[i-1], seq2[j-1], seq3[i+j-1], row[j]) \n",
+ " # extend by character from seq1\n",
+ " if previous_row[j] and seq1[i-1] == seq3[i+j-1]:\n",
+ " row[j] = True\n",
+ " backpointers[i, j] = (i-1, j, seq1[i-1], 'seq1') \n",
+ " if debug: print('seq1', i, j, seq1[i-1], seq2[j-1], seq3[i+j-1], row[j])\n",
+ " if not row[j]:\n",
+ " if debug: print('xxxx', i, j, seq1[i-1], seq2[j-1], seq3[i+j-1], row[j])\n",
+ " previous_row = row\n",
+ "\n",
+ " if return_backpointers:\n",
+ " retval = [row[-1]]\n",
+ " if return_backpointers:\n",
+ " retval += [backpointers]\n",
+ " return tuple(retval)\n",
+ " else:\n",
+ " return row[-1]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 22,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def is_interleave_rows2(seq1, seq2, seq3, return_backpointers=False, debug=False):\n",
+ " \"\"\"Return true if seq3 is some interleaved merge of seq1 and seq2.\n",
+ " If return_backpointers, also return the set of backpointers to\n",
+ " reconstruct the interleaving.\n",
+ " \n",
+ " This version doesn't keep the whole table, just the current and previous\n",
+ " rows. It also builds the current row as it goes along, rather than\n",
+ " building the whole row and updating elements as required.\"\"\"\n",
+ " \n",
+ " # dp_table[i, j] is True if first i+j characters of seq is made up of \n",
+ " # an interleaving of the first i characters of seq1 and the \n",
+ " # first j characters of seq2\n",
+ " \n",
+ " if len(seq1) + len(seq2) != len(seq3):\n",
+ " if return_backpointers:\n",
+ " retval = [False]\n",
+ " if return_backpointers:\n",
+ " retval += [{}]\n",
+ " return tuple(retval)\n",
+ " else:\n",
+ " return False\n",
+ " \n",
+ "\n",
+ " backpointers = {}\n",
+ "\n",
+ " for i in range(len(seq1)+1):\n",
+ " row = []\n",
+ " for j in range(len(seq2)+1):\n",
+ " if i == 0 and j == 0:\n",
+ " row += [True]\n",
+ " if debug: print('xxxx', i, j, '!', '!', '!', row[j])\n",
+ " elif i == 0:\n",
+ " # extend by character from seq2\n",
+ " if row[j-1] and seq2[j-1] == seq3[i+j-1]:\n",
+ " row += [True]\n",
+ " backpointers[i, j] = (i, j-1, seq2[j-1], 'seq2')\n",
+ " else:\n",
+ " row += [False]\n",
+ " if debug: print('seq2', i, j, '!', seq2[j-1], seq3[i+j-1], row[j])\n",
+ " elif j == 0:\n",
+ " # extend by character from seq1\n",
+ " if previous_row[j] and seq1[i-1] == seq3[i+j-1]:\n",
+ " row += [True]\n",
+ " backpointers[i, j] = (i-1, j, seq1[i-1], 'seq1')\n",
+ " else:\n",
+ " row += [False]\n",
+ " if debug: print('seq1', i, j, seq1[i-1], '!', seq3[i+j-1], row[j])\n",
+ " else:\n",
+ " # extend by character from seq2\n",
+ " if row[j-1] and seq2[j-1] == seq3[i+j-1]:\n",
+ " row += [True]\n",
+ " backpointers[i, j] = (i, j-1, seq2[j-1], 'seq2')\n",
+ " if debug: print('seq2', i, j, seq1[i-1], seq2[j-1], seq3[i+j-1], row[j]) \n",
+ " # extend by character from seq1\n",
+ " elif previous_row[j] and seq1[i-1] == seq3[i+j-1]:\n",
+ " row += [True]\n",
+ " backpointers[i, j] = (i-1, j, seq1[i-1], 'seq1') \n",
+ " if debug: print('seq1', i, j, seq1[i-1], seq2[j-1], seq3[i+j-1], row[j])\n",
+ " else:\n",
+ " row += [False]\n",
+ " if debug: print('xxxx', i, j, seq1[i-1], seq2[j-1], seq3[i+j-1], row[j])\n",
+ " previous_row = row\n",
+ "\n",
+ " if return_backpointers:\n",
+ " retval = [row[-1]]\n",
+ " if return_backpointers:\n",
+ " retval += [backpointers]\n",
+ " return tuple(retval)\n",
+ " else:\n",
+ " return row[-1]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 23,