如何确定从序列中删除子序列的所有可能方法？ [英] How can I determine all possible ways a subsequence can be removed from a sequence?
问题描述
鉴于两个序列 A 和 B ，我如何生成 B 可以从< B 中移除的所有可能方式的列表em> A ？
Given two sequences, A and B, how can I generate a list of all the possible ways that B can be removed from A?
例如，在JavaScript中，如果我有一个函数 removeSubSeq 取两个数组参数做了我想要的，它将按如下方式工作：
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]）将返回 [[2,1,3,1]，[1,2,3,1]，[1， 2,1,3]] 因为最后的4s会匹配，并且有3个可能的地方让1匹配
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]）将返回 [] 因为第二个参数实际上不是子序列
removeSubSeq([8,6,4,4], [6,4,8]) would return [] because the second argument is not actually a subsequence
removeSubSeq（[1,1,2]，[1]）将返回 [[1,2]，[1,2]] 因为有两种方法可以删除1，即使它导致重复
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 是结果的总长度，使用经典的最长的公共子序列算法。
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.
（箭头对应LCS到目前为止是否来自 LCS（X [i-1]，Y [j]）和/或LCS（X [i]，Y [j-1]）或LCS（X [i-1]，Y [j] -1]），请参阅定义功能。）
(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.)
例如：
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代码：
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'])));
这篇关于如何确定从序列中删除子序列的所有可能方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
