我怎样才能确定一个子序列可以从序列中删除的所有可能的方式？
给定两个序列A和B ，如何生成B可以从A中删除的所有可能方式的列表？
例如，在JavaScript中，如果我有一个functionremoveSubSeq采取两个数组参数，我想要的，它将工作如下：
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，即使它会导致重复
这个问题可以用O(n*m + r)时间来解决，其中r是结果的总长度，使用经典的最长公共子序列algorithm。
一旦创build了表格，就像在维基百科的例子中一样 ，用对angular线箭头的单元格列表replace它，这些列表也具有与其行对应的值。 现在从最后一行对angular线的每个单元格向后遍历，在string中累积相关索引并复制和分割累积，使得每个带有对angular线箭头的单元格在前一行中具有对angular线的所有单元格的延续就在它的左边（存储这个数字，就像你构buildmatrix一样），一个数值较less。 当累计达到零单元格时，拼接来自string的累计索引，并将结果作为结果添加。
（箭头对应于LCS到目前为止是来自LCS(X[i-1],Y[j]) and/or LCS(X[i],Y[j-1]), or LCS(X[i-1],Y[j-1]) ，请参阅函数定义 。）
例如：
0 agbabcc 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'])));
你可以使用recursion。 通过遍历A并按顺序推送元素来构build新的子序列C. 每当遇到一个匹配B头部的元素时，你就会把recursion分成两个path：一个是从A和B中删除（即跳过）元素，另一个是忽略它，继续像往常一样的业务。
如果用尽了所有的B（意味着你从A中删除了B中的所有元素），那么把A的其余部分附加到C将产生一个有效的子序列。 否则，如果到达A的末尾而不耗尽所有的B，则C不是有效的子序列，应该丢弃。
function removeSubSeq(a, b) { function* remove(i, j, c) { if (j >= b.length) { yield c.concat(a.slice(i)); } else if (i >= a.length) { return; } else if (a[i] === b[j]) { yield* remove(i + 1, j + 1, c); yield* remove(i + 1, j, c.concat(a.slice(i, i + 1))); } else { yield* remove(i + 1, j, c.concat(a.slice(i, i + 1))); } } if (a.length < b.length) { return []; } return Array.from(remove(0, 0, [])); }
通过用简单的push（）/ pop（）对replace每个recursion分支中Array.concat的使用，内部帮助函数可以变得稍微高效一些，但是这使得控制stream程更加难以理解。
function* remove(i, j, c) { if (j >= b.length) { yield c.concat(a.slice(i)); } else if (i >= a.length) { return; } else { if (a[i] === b[j]) { yield* remove(i + 1, j + 1, c); } c.push(a[i]); yield* remove(i + 1, j, c); c.pop(); } }
这个问题可以用自下而上的dynamic规划方法来解决。
让我们考虑一个recursion关系f(i1, i2) ，它有助于检查序列arr2的尾部是否可以从序列arr1的尾部去除：
f(i1, i2) = true, if(i1 == length(arr1) AND i2 == length(arr2)) f(i1, i2) = f(i1 + 1, i2) OR f(i1 + 1, i2 + 1), if(arr1[i1] == arr2[i2]) f(i1, i2) = f(i1 + 1, i2), if(arr1[i1] != arr2[i2]) solution = f(0, 0)
我使用术语tail来表示arr1的子序列，该序列从索引i1开始并跨越到arr1的末端（对于arr2是相同的 – arr2 尾巴从索引i2开始并跨越到arr2的末端）。
让我们从给定的recursion关系的自顶向下的实现开始（但是没有记忆，为了保持简单的解释）。 下面是Java代码片段，它删除arr2后打印所有可能的arr1序列：
void remove(int[] arr1, int[] arr2) { boolean canBeRemoved = remove(arr1, arr2, 0, 0, new Stack<>()); System.out.println(canBeRemoved); } boolean remove(int[] arr1, int[] arr2, int i1, int i2, Stack<Integer> stack) { if (i1 == arr1.length) { if (i2 == arr2.length) { // print yet another version of arr1, after removal of arr2 System.out.println(stack); return true; } return false; } boolean canBeRemoved = false; if ((i2 < arr2.length) && (arr1[i1] == arr2[i2])) { // current item can be removed canBeRemoved |= remove(arr1, arr2, i1 + 1, i2 + 1, stack); } stack.push(arr1[i1]); canBeRemoved |= remove(arr1, arr2, i1 + 1, i2, stack); stack.pop(); return canBeRemoved; }
所提供的代码片段不使用任何记忆技术，并且对于给定问题的所有实例具有指数运行时复杂度 。
但是，我们可以看到variablesi1只能具有区间[0..length(arr1)]的值，variablesi2也只能具有区间[0..length(arr2)] 。
因此，可以检查arr2是否可以从多个运行时复杂度的arr1移除： O(length(arr1) * length(arr2)) 。
另一方面，即使我们发现具有多项式运行时复杂性， arr2可以从arr1删除 – 仍然可能有指数级的arr2从arr1删除arr2 。
例如，考虑问题的实例：需要从arr1 = [1,1,1,1,1,1,1]删除arr2 = [1,1,1] arr1 = [1,1,1,1,1,1,1] 。 有7!/(3! * 4!) = 35种方式来做到这一点。
尽pipe如此，下面是具有回溯的自下而上的dynamic规划解决scheme，对于给定问题的许多实例来说仍将具有比指数更好的运行时复杂度：
void remove_bottom_up(int[] arr1, int[] arr2) { boolean[][] memoized = calculate_memoization_table(arr1, arr2); backtrack(arr1, arr2, 0, 0, memoized, new Stack<>()); } /** * Has a polynomial runtime complexity: O(length(arr1) * length(arr2)) */ boolean[][] calculate_memoization_table(int[] arr1, int[] arr2) { boolean[][] memoized = new boolean[arr1.length + 1][arr2.length + 1]; memoized[arr1.length][arr2.length] = true; for (int i1 = arr1.length - 1; i1 >= 0; i1--) { for (int i2 = arr2.length; i2 >= 0; i2--) { if ((i2 < arr2.length) && (arr1[i1] == arr2[i2])) { memoized[i1][i2] = memoized[i1 + 1][i2 + 1]; } memoized[i1][i2] |= memoized[i1 + 1][i2]; } } return memoized; } /** * Might have exponential runtime complexity. * * Eg consider the instance of the problem, when it is needed to remove * arr2 = [1,1,1] from arr1 = [1,1,1,1,1,1,1]. * * There are 7!/(3! * 4!) = 35 ways to do it. */ void backtrack(int[] arr1, int[] arr2, int i1, int i2, boolean[][] memoized, Stack<Integer> stack) { if (!memoized[i1][i2]) { // arr2 can't be removed from arr1 return; } if (i1 == arr1.length) { // at this point, instead of printing the variant of arr1 after removing of arr2 // we can just collect this variant into some other container // eg allVariants.add(stack.clone()) System.out.println(stack); return; } if ((i2 < arr2.length) && (arr1[i1] == arr2[i2])) { backtrack(arr1, arr2, i1 + 1, i2 + 1, memoized, stack); } stack.push(arr1[i1]); backtrack(arr1, arr2, i1 + 1, i2, memoized, stack); stack.pop(); }
描述解决scheme的JavaScript实现
function remove_bottom_up(base_arr, removed_arr) { // Initialize memoization table var memoized = new Array(base_arr.length + 1); for (var i = 0; i < base_arr.length + 1; i++) { memoized[i] = new Array(removed_arr.length + 1); } memoized[base_arr.length][removed_arr.length] = true; // Calculate memoization table for (var i1 = base_arr.length - 1; i1 >= 0; i1--) { for (var i2 = removed_arr.length; i2 >= 0; i2--) { if ((i2 < removed_arr.length) && (base_arr[i1] == removed_arr[i2])) { memoized[i1][i2] = memoized[i1 + 1][i2 + 1]; } memoized[i1][i2] |= memoized[i1 + 1][i2]; } } // Collect all variants var all_variants = []; backtrack(base_arr, removed_arr, 0, 0, memoized, [], all_variants); return all_variants; } function backtrack(base_arr, removed_arr, i1, i2, memoized, stack, all_variants) { if (!memoized[i1][i2]) { // arr2 can't be removed from arr1 return; } if (i1 == base_arr.length) { all_variants.push(stack.slice(0)); return; } if ((i2 < removed_arr.length) && (base_arr[i1] == removed_arr[i2])) { backtrack(base_arr, removed_arr, i1 + 1, i2 + 1, memoized, stack, all_variants); } stack.push(base_arr[i1]); backtrack(base_arr, removed_arr, i1 + 1, i2, memoized, stack, all_variants); stack.pop(); } console.log(JSON.stringify(remove_bottom_up([1, 2, 1, 3, 1, 4, 4], [1, 4, 4]))); console.log(JSON.stringify(remove_bottom_up([8, 6, 4, 4], [6, 4, 8]))); console.log(JSON.stringify(remove_bottom_up([1, 1, 2], [1]))); console.log(JSON.stringify(remove_bottom_up([1, 1, 1, 1, 1, 1, 1], [1, 1, 1])));
algorithm：
- 从B中的第一个元素开始recursion地构build节点树。每个节点的值是与其级别匹配的子序列项目的索引，其后代是下一个项目的索引 – 对于
[1,2,1,3,1,4,4], [1,4,4]树会是[ [ 0, [5, [6]], [6] ], [ 2, [5, [6]], [6] ], [ 4, [5, [6]], [6] ]。 - 走这棵树，build立删除项的子序列，即查找树中所有与子序列一样长的path。 这会产生一个像
[ [ 0, 5, 6 ], [ 2, 5, 6 ], [ 4, 5, 6 ] ]。 - 对于如此开发的每个列表，附加从被删除的索引处的元素得到的列表：
[ [ 2, 1, 3, 1 ], [ 1, 2, 3, 1 ], [ 1, 2, 1, 3 ] ]。
执行此操作的代码与您的所有testing用例相匹配：
#!/usr/bin/env node var _findSubSeqs = function(outer, inner, current) { var results = []; for (var oi = current; oi < outer.length; oi++) { if (outer[oi] == inner[0]) { var node = { value: oi, children: _findSubSeqs(outer, inner.slice(1), oi+1) }; results.push(node); } } return results; } var findSubSeqs = function(outer, inner) { var results = _findSubSeqs(outer, inner, 0); return walkTree(results).filter(function(a) {return (a.length == inner.length)}); } var _walkTree = function(node) { var results = []; if (node.children.length) { for (var n = 0; n < node.children.length; n++) { var res = _walkTree(node.children[n]) for (r of res) { results.push([node.value].concat(r)) } } } else { return [[node.value]] } return results } var walkTree = function(nds) { var results = []; for (var i = 0; i < nds.length; i++) { results = results.concat(_walkTree(nds[i])) } return results } var removeSubSeq = function(outer, inner) { var res = findSubSeqs(outer, inner); var subs = []; for (r of res) { var s = []; var k = 0; for (var i = 0; i < outer.length; i++) { if (i == r[k]) { k++; } else { s.push(outer[i]); } } subs.push(s); } return subs } console.log(removeSubSeq([1,2,1,3,1,4,4], [1,4,4])) console.log(removeSubSeq([8,6,4,4], [6,4,8]) ) console.log(removeSubSeq([1,1,2], [1]))
首先我会使用string。 操作更简单：
var results = []; function permute(arr) { var cur, memo = []; for (var i = 0; i < arr.length; i++) { cur = arr.splice(i, 1); if (arr.length === 0) { results.push(memo.concat(cur)); } permute(arr.slice(), memo.concat(cur)); arr.splice(i, 0, cur[0]); } return results; } function removeSub(arr, sub) { strArray = arr.join(' '); if(strArray.includes(sub)){ return strArray.replace(sub.join(' ')).split(' '); } return []; } function removeSubSeq(arr, sub) { return permute(removeSub(arr, sub)); }
我没有评论这些代码，但不要犹豫，要求澄清。 没有经过testing，但其中的想法是…
我的目标是尽可能less地创build和调用函数。 这似乎工作。 绝对可以清理。 一些东西玩…
function removeSubSeq( seq, sub ) { var arr, sub_v, sub_i = 0, seq_i, sub_len = sub.length, sub_lenm1 = sub_len - 1, seq_len = seq.length, pos = {}, pos_len = [], c_pos, map_i = [], len, r_pos, sols = [], sol; do { map_i[ sub_i ] = 0; sub_v = sub[ sub_i ]; if( pos[ sub_v ] ) { pos_len[ sub_i ] = pos_len[ sub_i - 1 ]; continue; } arr = pos[ sub_v ] = []; c_pos = 0; seq_i = seq_len; while( seq_i-- ) { if( seq[ seq_i ] === sub_v ) { arr[ c_pos++ ] = seq_i; } } pos_len[ sub_i ] = arr.length; } while( ++sub_i < sub_len ); len = pos[ sub[ 0 ] ].length; while( map_i[ 0 ] < len ) { sub_i = 0; arr = []; do { r_pos = pos[ sub[ sub_i ] ][ map_i[ sub_i ] ]; if( sub_i && r_pos <= arr[ sub_i - 1] ) break; arr.push( r_pos ); } while( ++sub_i < sub_len ); if( sub_i === sub_len ) { sol = seq.slice( 0 ); while( sub_i-- ) sol.splice( arr[ sub_i ], 1 ); sols.push( sol ); } sub_i = sub_lenm1; while( ++map_i[ sub_i ] === pos_len[ sub_i ] ) { if( sub_i === 0 ) break; map_i[ sub_i-- ] = 0; } } while( map_i[ 0 ] < len ); return sols; } console.log(JSON.stringify(removeSubSeq([1,2,1,3,1,4,4], [1,4,4]))); console.log(JSON.stringify(removeSubSeq([8,6,4,4], [6,4,8]))); console.log(JSON.stringify(removeSubSeq([1,1,2], [1]))); console.log(JSON.stringify(removeSubSeq(['a','g','b','a','b','c','c'], ['a','b','c'])));
