heenenee - 1 year ago 55

Javascript 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`

`removeSubSeq([1,2,1,3,1,4,4], [1,4,4])`

`[ [2,1,3,1], [1,2,3,1], [1,2,1,3] ]`

`removeSubSeq([8,6,4,4], [6,4,8])`

`[]`

`removeSubSeq([1,1,2], [1])`

`[ [1,2], [1,2] ]`

Answer Source

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],1 + lcs[i][j-1][1]];
if (lcs[i][j][0] == i){
// [arr index, left node count above]
var node = [j - 1,lcs[i-1][j-1][1]];
nodes[i].push(node);
}
} 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'])));
```