renderizado - quitar el javascript que bloquea la visualización de contenido wp rocket
¿Cómo puedo determinar todas las formas posibles en que se puede eliminar una subsecuencia de una secuencia? (6)
Dadas dos secuencias, A y B , ¿cómo puedo generar una lista de todas las formas posibles en que B puede eliminarse de A ?
Por ejemplo, en JavaScript, si tuviera una función removeSubSeq tomando dos argumentos de matriz que hicieran lo que quisiera, funcionaría de la siguiente manera:
removeSubSeq([1,2,1,3,1,4,4], [1,4,4]) devolvería [ [2,1,3,1], [1,2,3,1], [1,2,1,3] ] porque los 4s al final coincidirían, y hay tres posibles lugares para que el 1 coincida
removeSubSeq([8,6,4,4], [6,4,8]) devolvería [] porque el segundo argumento no es en realidad una subsecuencia
removeSubSeq([1,1,2], [1]) devolverá [ [1,2], [1,2] ] porque hay dos maneras en que se puede eliminar el 1, aunque resulte en duplicados
El algoritmo:
- Recursivamente construya un árbol de nodos, comenzando desde el primer elemento en B. El valor de cada nodo es el índice de la subsecuencia que coincide con su nivel y sus descendientes son los índices del siguiente elemento, por lo que para
[1,2,1,3,1,4,4], [1,4,4]el árbol sería[ [ 0, [5, [6]], [6] ], [ 2, [5, [6]], [6] ], [ 4, [5, [6]], [6] ]. - Recorre este árbol y crea subsecuencias de elementos para eliminar, es decir, busca todas las rutas en el árbol que sean tan largas como la subsecuencia. Esto daría como resultado una lista como
[ [ 0, 5, 6 ], [ 2, 5, 6 ], [ 4, 5, 6 ] ]. - Para cada lista así desarrollada, anexe la lista que resulta de los elementos en los índices que se eliminan:
[ [ 2, 1, 3, 1 ], [ 1, 2, 3, 1 ], [ 1, 2, 1, 3 ] ]
El código para hacer esto, que coincide con todos sus casos de prueba:
#!/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]))
Este problema se puede resolver en O(n*m + r) tiempo, donde r es la longitud total de los resultados, utilizando el clásico algoritmo de subsecuencia común más largo .
Una vez hecha la tabla, como en el example de Wikipedia, reemplácela con una lista de celdas con una flecha diagonal que también tenga un valor correspondiente a su fila. Ahora recorra hacia atrás desde cada celda con una diagonal en la última fila, acumulando el índice relevante en la cadena y duplicando y dividiendo la acumulación de modo que cada celda con una flecha diagonal tendrá una continuación para todas las celdas con una diagonal en la fila anterior que están a la izquierda de ella (store that count también, mientras construyes la matriz) y uno menos en valor. Cuando una acumulación llega a cero, empalme los índices acumulados de la cadena y añádalos como resultado.
(Las flechas corresponden con si el LCS hasta ahora proviene de LCS(X[i-1],Y[j]) and/or LCS(X[i],Y[j-1]), or LCS(X[i-1],Y[j-1]) , vea la definition la función.)
Por ejemplo:
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
Código de 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''])));
Este problema se puede resolver usando el enfoque de programación dinámica ascendente con retroceso .
Consideremos una relación de recurrencia f(i1, i2) , que ayuda a verificar si la cola de la secuencia arr2 se puede eliminar de la cola de la secuencia 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)
Uso el término cola para denotar la subsecuencia de arr1 que comienza en el índice i1 y se extiende hasta el final de arr1 (y lo mismo para arr2 - la cola de arr2 comienza en el índice i2 y se extiende hasta el final de arr2 ).
Comencemos con la implementación de arriba hacia abajo de la relación de recurrencia dada (aunque sin memoria, para mantener la explicación simple). A continuación se muestra el fragmento de código de Java, que imprime todas las subsecuencias posibles de arr1 después de la eliminación de 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;
}
El fragmento de código provisto no utiliza ninguna técnica de memorización, y tiene la complejidad de tiempo de ejecución exponencial para todas las instancias del problema dado .
Sin embargo, podemos ver que la variable i1 solo puede tener el valor del intervalo [0..length(arr1)] , también la variable i2 solo puede tener el valor del intervalo [0..length(arr2)] .
Por lo tanto, es posible verificar si arr2 puede eliminarse de arr1 con complejidad de tiempo de ejecución polinomial: O(length(arr1) * length(arr2)) .
Por otro lado, incluso si encontramos con la complejidad de tiempo de ejecución polinomial que arr2 se puede eliminar de arr1 , todavía podría haber una cantidad exponencial de formas posibles de eliminar arr2 de arr1 .
Por ejemplo, considere la instancia del problema: cuando es necesario eliminar arr2 = [1,1,1] de arr1 = [1,1,1,1,1,1,1] . Hay 7!/(3! * 4!) = 35 formas de hacerlo.
Sin embargo, a continuación se muestra la solución de Programación Dinámica ascendente con retroceso , que para muchas instancias de un problema dado tendrá una mejor complejidad de tiempo de ejecución que exponencial:
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();
}
Implementación de JavaScript de la solución descrita
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])));
Mi objetivo era crear y llamar funciones lo menos posible. Esto parece funcionar Definitivamente podría ser limpiado. Algo para jugar con ...
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''])));
Primero usaría una cuerda. Es más fácil de manipular:
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));
}
No he comentado el código, pero no dude en pedir una aclaración. No está probado, pero la idea está en eso ...
Puedes usar la recursividad. Construya una nueva subsecuencia C caminando a través de A y empujando los elementos en orden. Cada vez que encuentre un elemento que coincida con el encabezado de B, dividirá la recursión en dos caminos: uno en el que elimina (es decir, omite) el elemento de A y B, y otro en el que lo ignora y continúa con las actividades habituales.
Si agotas todo B (lo que significa que "eliminaste" todos los elementos en B de A), entonces al agregar el resto de A a C se producirá una subsecuencia válida. De lo contrario, si llega al final de A sin agotar todo B, C no es una subsecuencia válida y debe descartarse.
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, []));
}
La función auxiliar interna se puede hacer un poco más eficiente reemplazando el uso de Array.concat en cada rama recursiva con un par simple push () / pop (), aunque esto hace que el control fluya un poco más difícil de asimilar.
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();
}
}