给定两个序列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，即使这会导致重复。
使用经典的 最长公共子序列 算法，可以在 O(n*m + r) 的时间内解决此问题。其中，r 是结果的总长度。
一旦表格生成，就像维基百科的示例中那样，将其替换为具有对角线箭头并且还具有与其行对应的值的单元格列表。现在从最后一行中具有对角线的每个单元格开始向后遍历，累加字符串中的相关索引，并复制和拆分累加，使得每个带有对角线箭头的单元格都将延续到前面的行中所有带有对角线的单元格，而这些单元格位于它的左侧（在构建矩阵时也将该计数存储下来），值减少一个。当累积达到零单元格时，从字符串中剪切累积的索引，并将其作为结果添加。
（箭头对应于迄今为止的LCS是否来自LCS(X[i-1],Y[j]) 和/或 LCS(X[i],Y[j-1])，或 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'])));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() 对替换使用 Array.concat，可以使内部辅助函数略微更有效率，尽管这会使控制流变得有些难以理解。
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();
}
}
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)
arr1结尾的子序列（arr2的尾部也类似 - arr2的尾部从索引i2开始并跨越到arr2的结尾）。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;
}
[0..length(arr1)]，变量i2也只能取值自区间[0..length(arr2)]。O(length(arr1) * length(arr2))来检查是否可以从arr1中删除arr2。arr2可以从arr1中删除，仍然可能有指数数量的可能方式来删除arr2从arr1中。arr1 = [1,1,1,1,1,1,1]中删除arr2=[1,1,1]。这样做有35种方法：7!/(3! * 4!) = 35。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.
*
* E.g. 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
// e.g. 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();
}
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])));[1,2,1,3,1,4,4], [1,4,4]，树将是[ [ 0, [5, [6]], [6] ], [ 2, [5, [6]], [6] ], [ 4, [5, [6]], [6] ]。[ [ 0, 5, 6 ], [ 2, 5, 6 ], [ 4, 5, 6 ] ]这样的列表。[ [ 2, 1, 3, 1 ], [ 1, 2, 3, 1 ], [ 1, 2, 1, 3 ] ]。#!/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]))
首先，我会使用字符串。它更容易操作：
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));
}
我没有对代码进行注释，但是如果需要可以随时向我询问。代码尚未经过测试，但是其中包含了一个思路...
return permute(removeSub(arr, sub) 处缺少闭合的 )。 - guest271314我的目标是尽可能少地创建和调用函数。 这似乎有效。 肯定可以整理得更好。 值得一试...
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'])));