如何确定序列中可以删除子序列的所有可能方法？(How can I determine all possible ways a subsequence can be removed from a seq

如何确定序列中可以删除子序列的所有可能方法？(How can I determine all possible ways a subsequence can be removed from a sequence?)

给出两个序列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] ]因为最后的4s将匹配，并且有1个匹配的三个可能的位置

removeSubSeq([8,6,4,4], [6,4,8])将返回[]因为第二个参数实际上不是一个子序列

removeSubSeq([1,1,2], [1])将返回[ [1,2], [1,2] ]因为有两种方法可以删除1，即使它导致重复

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

最满意答案

这个问题可以在O(n*m + r)时间内解决，其中r是结果的总长度，使用经典的最长公共子序列算法。

一旦制作了表格，就像在维基百科的例子中一样 ，用一个对角箭头替换它的单元格列表，该箭头也有一个与它们的行对应的值。 现在，从最后一行中的对角线向后遍历每个单元格，将相关索引累加到字符串中，并复制和分割累加，以使每个具有对角线箭头的单元格将具有对前一行中具有对角线的所有单元格的延续，在它的左边（存储那个数，以及，当你建立矩阵）和一个较少的价值。 当积累达到零单元格时，从字符串中拼接累积的索引，并将其添加到结果中。

（这些箭头与LCS(X[i-1],Y[j]) and/or LCS(X[i],Y[j-1]), or LCS(X[i-1],Y[j-1]) ，请参见功能定义 。）

例如：

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