javascript - 如何确定从序列中删除子序列的所有可能方式？

给定两个序列A和B，我如何生成可以从A中删除B的所有可能方式的列表？

例如，在JavaScript中，如果我有一个函数removeSubSeq接受了两个满足我需要的数组参数，它将按以下方式工作:
removeSubSeq([1,2,1,3,1,4,4], [1,4,4])将返回[ [2,1,3,1], [1,2,3,1], [1,2,1,3] ]，因为末尾的4将匹配，并且1匹配的位置可能有三个
removeSubSeq([8,6,4,4], [6,4,8])将返回[]，因为第二个参数实际上不是子序列
removeSubSeq([1,1,2], [1])将返回[ [1,2], [1,2] ]，因为有两种方法可以删除1，即使它导致重复

最佳答案

可以使用longest common subsequence算法在O(n*m + r)时间内解决此问题，其中r是结果的总长度。

制成表格后，如Wikipedia的example所示，将其替换为带有对角箭头的单元格列表，该单元格也具有与行对应的值。现在从最后一行中对角线的每个像元向后遍历，在字符串中累加相关索引，然后对累加进行复制和分割，以使每个带有对角线箭头的像元都延续到前一行中所有对角线的像元。位于其左侧(在构建矩阵时也要存储该计数)，并且值减少一。当累加达到零单元格时，从字符串中拼接累加的索引并将其添加为结果。

(箭头与到目前为止LCS是否来自LCS(X[i-1],Y[j]) and/or LCS(X[i],Y[j-1]), or LCS(X[i-1],Y[j-1])相对应，请参见函数definition。)

例如:

  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代码:

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'])));