hee*_*nee 42 javascript algorithm 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,即使它会导致重复
גלע*_*רקן 18
这个问题可以及时解决,使用经典的最长公共子序列算法,结果的总长度O(n*m + r)在哪里.r
一旦制作完表格,就像在维基百科的例子中一样,将其替换为具有对角线箭头的单元格列表,该箭头也具有与其行对应的值.现在从最后一行中的对角线向后遍历每个单元格,在字符串中累积相关索引并复制和分割累积,使得每个具有斜箭头的单元格将具有前一行中具有对角线的所有单元格的延续,在它的左边(存储也计算,当你构建矩阵)和一个较少的值.当累积达到零单元时,从字符串中拼接累积的索引并将其作为结果添加.
(箭头对应到目前为止LCS是否来自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'])));你可以使用递归.通过遍历A并按顺序推送元素来构建新的子序列C. 每当遇到与B的头部匹配的元素时,您将把递归分成两个路径:一个用于从A和B中删除(即跳过)元素,另一个用于忽略它,并像往常一样继续工作.
如果你耗尽所有B(意味着你从A中删除了B中的所有元素),那么将A的其余部分附加到C将产生有效的子序列.否则,如果在没有耗尽所有B的情况下到达A的末尾,则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, []));
}
通过使用Array.concat简单的push()/ pop()对替换每个递归分支中的使用,可以使内部辅助函数稍微更有效,但这会使控制流更难以理解.
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),它有助于检查序列的尾部是否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- 在索引处开始的尾部并跨越到结尾).arr2i2arr2
让我们从给定的递归关系的自上而下的实现开始(但没有memoization,以保持解释简单).下面是Java代码片段,它打印了arr1删除后的所有可能的子序列arr2:
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;
}
提供的代码片段不使用任何memoization技术,并且对于给定问题的所有实例具有指数运行时复杂性.
但是,我们可以看到变量i1只能有间隔的值[0..length(arr1)],变量i2也只能有间隔的值[0..length(arr2)].
因此,可以检查是否arr2可以从arr1多项式运行时复杂性中删除:O(length(arr1) * length(arr2)).
在另一方面,即使我们找到多项式运行的复杂性是arr2可以被删除的arr1-还有可能是一个可能的方式去除量指数arr2从arr1.
例如,考虑问题的实例:当需要清除arr2 = [1,1,1]从arr1 = [1,1,1,1,1,1,1].有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])));