How can I determine all possible ways a subsequence can be removed from a sequence?

Question

Given two sequences, A and B, how can I generate a list of all the possible ways that B can be removed from A?

For example, In JavaScript, if I had a function removeSubSeq taking two array arguments that did what I want, it would work as follows:

removeSubSeq([1,2,1,3,1,4,4], [1,4,4]) would return [ [2,1,3,1], [1,2,3,1], [1,2,1,3] ] because the 4s at the end would match, and there are three possible places for the 1 to match

removeSubSeq([8,6,4,4], [6,4,8]) would return [] because the second argument is not actually a subsequence

removeSubSeq([1,1,2], [1]) would return [ [1,2], [1,2] ] because there's two ways that the 1 could be removed, even though it results in duplicates

Answer 1

This problem can be solved in O(n*m + r) time, where r is the total length of the results, using the classic longest common subsequence algorithm.

Once the table is made, as in Wikipedia's example, replace it with a list of the cells with a diagonal arrow that also have a value corresponding with their row. Now traverse backwards from each cell with a diagonal in the last row, accumulating the relevant index in the string and duplicating and splitting the accumulation such that each cell with a diagonal arrow will have a continuation to all cells with a diagonal in the preceding row that are to the left of it (store that count as well, as you build the matrix) and one less in value. When an accumulation reaches a zero cell, splice the accumulated indexes from the string and add that as a result.

(The arrows correspond with whether the LCS so far came from LCS(X[i-1],Y[j]) and/or LCS(X[i],Y[j-1]), or LCS(X[i-1],Y[j-1]), see the function definition.)

For example:

  0  a  g  b  a  b  c  c 0 0  0  0  0  0  0  0  0 a 0 ↖1  1  1 ↖1  1  1  1 b 0  1  1 ↖2  2 ↖2  2  2 c 0  1  1  2  2  2 ↖3 ↖3 

JavaScript code:

function remove(arr,sub){    var _arr = [];    arr.forEach(function(v,i){ if (!sub.has(i)) _arr.push(arr[i]); });    return _arr;  }    function f(arr,sub){    var res = [],        lcs = new Array(sub.length + 1),        nodes = new Array(sub.length + 1);           for (var i=0; i<sub.length+1;i++){      nodes[i] = [];      lcs[i] = [];           for (var j=0; j<(i==0?arr.length+1:1); j++){        // store lcs and node count on the left        lcs[i][j] = [0,0];      }    }       for (var i=1; i<sub.length+1;i++){       for (var j=1; j<arr.length+1; j++){        if (sub[i-1] == arr[j-1]){          lcs[i][j] = [1 + lcs[i-1][j-1][0],lcs[i][j-1][1]];                   if (lcs[i][j][0] == i){                    // [arr index, left node count above]            nodes[i].push([j - 1,lcs[i-1][j-1][1]]);                     lcs[i][j][1] += 1;          }                 } else {          lcs[i][j] = [Math.max(lcs[i-1][j][0],lcs[i][j-1][0]),lcs[i][j-1][1]];        }      }    }         function enumerate(node,i,accum){      if (i == 0){        res.push(remove(arr,new Set(accum)));        return;      }            for (var j=0; j<node[1]; j++){        var _accum = accum.slice();        _accum.push(nodes[i][j][0]);                enumerate(nodes[i][j],i - 1,_accum);      }    }        nodes[sub.length].forEach(function(v,i){       enumerate(nodes[sub.length][i],sub.length - 1,[nodes[sub.length][i][0]]);     });      return res;  }    console.log(JSON.stringify(f([1,2,1,3,1,4,4], [1,4,4])));  console.log(JSON.stringify(f([8,6,4,4], [6,4,8])));  console.log(JSON.stringify(f([1,1,2], [1])));  console.log(JSON.stringify(f(['a','g','b','a','b','c','c'], ['a','b','c'])));