javascript - especifico - eliminar un elemento de un arreglo en java

Algoritmo para determinar todas las formas posibles en que se puede eliminar un grupo de valores de una secuencia

Question

Estoy tratando de determinar cuántas maneras diferentes puedo eliminar un grupo de valores de una secuencia, dejando la secuencia original en orden (estable) y asegurándome de eliminar solo 1 valor de instancia de la secuencia original. Por ejemplo, si tuviera [1,2,1,3,1,4,4] y quisiera eliminar [1,4,4] mis combinaciones resultantes serían:

[1,2,1,3,1,4,4] / [1,4,4] = [ [2,1,3,1], [1,2,3,1], [1,2,1,3] ]

o [1,2,1,3,1,4,4] / [1,1] = [ [2,3,1,4,4], [1,2,3,4,4], [2,1,3,4,4] ]

Tengo el código de JavaScript que escribí para generar combinaciones de todos los valores de matriz sin eliminar y la parte de eliminación parece que debería ser fácil, pero no veo el algoritmo cuando es necesario eliminar varios valores varias veces.

Answer 1

Esto se puede hacer con combinatoria simple.

Para simplificar, digamos que los valores en la lista original son 1,2,3,...,n .
Deje a[i] ser el número de ocurrencias de i en la lista original.
Deje b[i] ser el número de ocurrencias de i en la lista de eliminaciones de valores

El número de opciones para reducir i es Choose(a[i],b[i]) = a[i]!/((a[i]-b[i])!b[i]!)

Como combina todos estos en el cierre "Y", el número total de posibilidades es:

Choose(a[1],b[1]) * Choose(a[2],b[2]) * ... * Choose(a[n], b[n])

En cuanto a los valores que no están en el conjunto de reducción, no necesita preocuparse por ellos. ya que su valor en b list será 0, y Choose(x,0) = 1 para todo x

Esto le deja una solución de tiempo lineal (suponiendo que puede calcular Elegir (.,.) En tiempo constante después de hacer un preprocesamiento para almacenar en caché los valores factoriales.

En tu ejemplo tienes:

a = [3, 1, 1, 2]
b = [1, 0, 0, 2]
Choose(3,1) = 3
Choose(1,0) = 1
Choose(1,0) = 1
Choose(2,2) = 1
#number_possibilities = 3 * 1 * 1 * 1 = 3

Answer 2

Creo que Branching and Pruning es la forma ortodoxa de resolver este problema y con mucha posibilidad de optimización.
Pero, si solo quieres una solución simple e intuitiva. Aquí está.

Primero, encuentre los números que están en la lista de eliminación.
[1,2,1,3,1,4,4] [1,4,4]
de esto obtenemos [1,1,1,4,4]
En segundo lugar, elija tantos elementos de la lista de eliminación del primer paso, que es la combinación 5C3.
de esto obtenemos [1,1,1] [1,1,4] [1,4,4] ...
Tercero, compara la secuencia. entonces, obtienes el resultado.
Aquí está el código. Lo siento está en C ++, y utilicé una biblioteca de combinación simple.

#include<vector>
#include<algorithm>
#include<iostream>
#include"combi.h"
using namespace std;
int main()
{
vector<int> list {1,2,1,3,1,4,4};
vector<int> to_remove {1,4,4};
vector<int> index;
for(int i=0; i<list.size(); i++) {
if(find(to_remove.begin(), to_remove.end(), list[i]) != to_remove.end())
index.push_back(i);//insert index
}
bool sequence;
nCr ncr(index.size(), to_remove.size());
while(ncr.next()) {
sequence = true;
for(int i=0; i<ncr.size(); i++)
if(list[index[ncr[i]-1]] != to_remove[i]) sequence = false;
if(sequence) {
for(int i=0, j=0; i<list.size(); i++) {
if(i == index[ncr[j]-1]) j++;
else cout << list[i] << '' '';
}
cout << endl;
}
}
}

Aquí está la biblioteca de combinación.

class Combination
{
public:
Combination(int n, int r);
virtual ~Combination() { delete [] ar;}
int& operator[](unsigned i) {return ar[i];}
bool next();
int size() {return r;}
protected:
int* ar;
int n, r;
};
class nCr : public Combination
{
public:
nCr(int n, int r);
bool next();
};
Combination::Combination(int n, int r)
{
ar = new int[r];
this->n = n;
this->r = r;
}
nCr::nCr(int n, int r) : Combination(n, r)
{
if(r == 0) return;
for(int i=0; i<r-1; i++) ar[i] = i + 1;
ar[r-1] = r-1;
}
bool nCr::next()
{
if(r == 0) return false;
ar[r-1]++;
int i = r-1;
while(ar[i] == n-r+2+i) {
if(--i == -1) return false;
ar[i]++;
}
while(i < r-1) ar[i+1] = ar[i++] + 1;
return true;
}

Answer 3

Buen ejercicio, como de costumbre, toma 1 timeunits para codificar y 10 para escribir :-). No puedo cumplir con la restricción del idioma, ya que uso un idioma aún por nombrar , por lo tanto, puedo estar fuera de la competencia. Pero voy a desafiar a todos los que proporcionaron una solución con una verificación de corrección . Perdón por omitir las comas. Por favor verifique con estos argumentos:

[1 2 1 3 1 4 4] / [1 4 4 1]

debe producir las siguientes soluciones:

(2 3 1)(2 1 3)(1 2 3) 

Y

[1 2 1 3 1 4 4] / [1 4 4 1 1]

debe producir la siguiente solución:

(2 3)

Y

[1 1 1 1 1] / [1 1 1]

debería (imho) producir la siguiente solución:

(1 1)

Y

[1] / [2]

debería (imho) producir la siguiente solución:

[zero-length array]

Y

[1 2 1 1 4 4 3 8 6 4 1 1 4 3 2 1] / [1 1 4 1 1 1 3 4 8 6 2 2 4]

debe producir las siguientes soluciones:

(4 3 1)(3 4 1)(1 4 3)(3 1 4)(4 1 3)(1 3 4) 

SOLUCIÓN:

Esto no será lo más simple de implementar, aunque es bastante claro lógicamente. Estoy usando el término "subarreglo", como este:

(1 2 3)(4 5 6)(7 8 9 10) <- Array with 3 "sub-arrays", 3 "elements"

Paso 1 : asignar los argumentos (siguiendo el ejemplo original)

arg = 1,2,1,3,1,4,4
vec = 1,4,4 

Paso 2 : comprueba los únicos en vec y cuántos de ellos hay.

A = 1,4 // The uniques in vec
B = 1,2 // Occurances of them

Paso 3 : compilar índices en arg para cada uno de A (origen 1):

C = (1 3 5)(6 7) // 1 appears at indexes 1,3,5 in arg, 4 appears at indexes 6,7

Paso 4 : toma cada elemento de C cada elemento de B veces:

D = (1 3 5)(6 7)(6 7) // B is (1,2) so we take (1 3 5) once and (6 7) twice.

Paso 5 : (El paso complicado) Crea todas las combinaciones de elementos en D, usando una combinación externa:

Esto ocurre al crear primero todas las combinaciones de los dos elementos más a la derecha , es decir. (6 7) y (6 7):

(6 6)(6 7)(7 6)(7 7) // (6 7) combined with (6 7) all possible ways

Luego combine esto con la siguiente D (hacia la izquierda , eso es):

E = (1 6 6)(1 6 7)(1 7 6)(1 7 7)(3 6 6)(3 6 7)(3 7 6)(3 7 7)(5 6 6)(5 6 7)(5 7 6)(5 7 7) // (1 3 5) combined with (6 6)(6 7)(7 6)(7 7) all possible ways

Si hubiera más elementos en D, los tomaríamos uno por uno (hacia la izquierda) y combinaríamos con las combinaciones logradas hasta el momento. Hasta que todos los elementos de D estén hechos (donde "elemento" es una "sub-matriz").

Paso 6 : Elimine dichos elementos de E que contengan números duplicados "dentro" (por ejemplo, el elemento (1 6 6) se eliminará):

F = (1 6 7)(1 7 6)(3 6 7)(3 7 6)(5 6 7)(5 7 6) // What is left from E

Paso 7 : elimine de F, cuando las sub-matrices están ordenadas internamente, tales elementos que son duplicados:

(1 6 7)(1 6 7)(3 6 7)(3 6 7)(5 6 7)(5 6 7) // F with sub-arrays sorted internally
G = (1 6 7)(3 6 7)(5 6 7) // Duplicate sub-arrays removed

Paso 8 : ¡Casi listo! Lo que tenemos ahora son los "no índices" en arg, aquellos índices que deben excluirse.

arg tiene 7 elementos, por lo tanto todos los índices en él son (1,2,3,4,5,6,7).

Escogiendo el primer elemento de G arriba, (1 6 7), significa que los índices (1 2 3 4 5 6 7) sin (1 6 7) es la primera respuesta. Todas las respuestas / índices:

(1 2 3 4 5 6 7) without (1 6 7) -> (2 3 4 5). arg[2 3 4 5] is (2 1 3 1)
(1 2 3 4 5 6 7) without (3 6 7) -> (1 2 4 5). arg[1 2 4 5] is (1 2 3 1)
(1 2 3 4 5 6 7) without (5 6 7) -> (1 2 3 4). arg[1 2 3 4] is (1 2 1 3)

Por lo tanto, las respuestas son

(2 1 3 1)(1 2 3 1)(1 2 1 3) 

Paso 9 : (Opcional) La respuesta puede contener duplicados a nivel de elemento. Conservar solo los únicos.

Puedes probar este Dyalog APL one-liner en tryapl.org :

1 2 1 3 1 4 4 {↑∪{c[b~⍵]}¨{(∊⍵≡¨∪¨⍵)/⍵},⊃∘.,/(+/¨a=¨⊂⍵)/((a←∪⍵)=¨⊂⍺)/¨⊂b←⍳⍴c←⍺} 1 4 4

Pega y presiona [enter], obtienes:

2 1 3 1
1 2 3 1
1 2 1 3

No podrá probar la muestra impugnada más larga anterior, ya que excede la asignación de tiempo de procesamiento disponible del servidor tryapl, pero puede probar con argumentos más cortos.

Answer 4

(Debido a que no estaba claro en la versión original de la pregunta si quiso eliminar una subsecuencia o una lista desordenada, actualicé mi respuesta para abordar ambos casos).

1. Eliminar una subsecuencia en orden

Obtenemos una secuencia de valores, por ejemplo [1,5,1,3,4,2,3,2,1,3,1,2] , y una [1,5,1,3,4,2,3,2,1,3,1,2] de valores a eliminar de la primera secuencia, por ejemplo [1,3,2,1] . Si encontramos donde cada instancia de los valores se encuentra en la secuencia, obtenemos un gráfico como este:

Encontrar todas las formas en que los valores se pueden eliminar de la secuencia, en este orden, significa encontrar todas las formas en que los valores a eliminar en la fila inferior se pueden conectar a una instancia en la secuencia, sin cruzar líneas, p.ej:

Para evitar la eliminación de valores de una manera que no conduzca a una solución válida (por ejemplo, comenzando por eliminar el valor más a la derecha 1, después del cual no hay ningún valor 3 que se pueda eliminar), primero eliminaremos todas las conexiones en el gráfico que conducen a soluciones tan inválidas.

Esto se hará iterando sobre la subsecuencia dos veces. Primero hacemos esto de izquierda a derecha, y para cada valor, miramos su conexión más a la izquierda, y eliminamos cualquier conexión del valor a su derecha que cumple o cruza esa conexión; por ejemplo, cuando se considera la conexión más a la izquierda desde el valor 2, se eliminan dos conexiones del valor 1 a su derecha (que se indican en rojo) porque cruzan esta conexión:

En el siguiente paso vamos de derecha a izquierda, y para cada valor, miramos su conexión más a la derecha, y eliminamos cualquier conexión del valor a la izquierda que cumple o cruza esa conexión; por ejemplo, al considerar la conexión más a la derecha desde el valor 1 a la derecha, la conexión más a la derecha desde el valor 2 a su izquierda (indicada en rojo) se elimina porque cruza esta conexión:

Luego terminamos con el gráfico simplificado que se muestra a continuación. Las combinaciones se realizan combinando cada instancia conectada de cada valor en la subsecuencia, utilizando, por ejemplo, la recursión: se repiten las opciones para el primer valor en la subsecuencia, y cada vez recurse con el resto de la subsecuencia , de modo que la opción para el primer valor se combina con todas las opciones para los otros valores.

Puede haber conexiones cruzadas en el gráfico simplificado, pero éstas ya no son problemáticas. En el ejemplo, verá que incluso si se elige la conexión correcta para el valor 3, hay una conexión para el valor 2 que no se cruza con él:

Convertir esto en código es relativamente sencillo; debajo del fragmento de código encontrará un recorrido del código con los datos del ejemplo.

function removeSubSeq(seq, sub) {
var posi = []; // list position of values in seq, then connect to positions in sub
sub.forEach(function(elem) {posi[elem] = []});
seq.forEach(function(elem, index) {if (posi[elem]) posi[elem].push(index)});
var conn = sub.map(function(elem) {return posi[elem].slice()});
for (var i = 1; i < conn.length; i++) {
var left = conn[i - 1][0];
while (conn[i][0] <= left) {
conn[i].shift(); // remove crossed connection left-to-right
}
}
for (var i = conn.length - 2; i >= 0; i--) {
var right = conn[i + 1][conn[i + 1].length - 1];
while (conn[i][conn[i].length - 1] >= right) {
conn[i].pop(); // remove crossed connection right-to-left
}
}
var combinations = [], result = [];
combine(0, -1, []); // initiate recursion to find combinations
for (var i = 0; i < combinations.length; i++) {
result[i] = seq.slice(); // create copies of seq and remove values
for (var j = combinations[i].length - 1; j >= 0; j--) {
result[i].splice(combinations[i][j], 1);
}
}
return result;
function combine(step, prev, comb) { // generate combinations using recursion
for (var i = 0; i < conn[step].length; i++) {
var curr = conn[step][i];
if (prev >= curr) continue; // skip crossed connection
if (step + 1 == conn.length) combinations.push(comb.concat([curr]));
else combine(step + 1, curr, comb.concat([curr]));
}
}
}
var result = removeSubSeq([1,5,1,3,4,2,3,2,1,3,1,2], [1,3,2,1]);
for (var i in result) document.write(result[i] + "<br>");

El código realiza estos pasos:

• Cree una matriz asociativa de la posición de instancias de cada valor presente en sub:

posi[1] = [0,2,8,10], posi[2] = [5,7,11], posi[3] = [3,6,9]} 

• Cree una matriz 2D que vincule las posiciones en la subsecuencia con las de la secuencia:

conn = [[0,2,8,10],[3,6,9],[5,7,11],[0,2,8,10]] 

• Examine la matriz de izquierda a derecha y elimine las conexiones cruzadas:

conn = [[0,2,8,10],[3,6,9],[5,7,11],[8,10]]

• Examine la matriz de derecha a izquierda y elimine las conexiones cruzadas:

conn = [[0,2],[3,6],[5,7],[8,10]]

• Genera todas las combinaciones de las posiciones usando recursión:

combinations = [[0,3,5,8],[0,3,5,10],[0,3,7,8],[0,3,7,10],
[0,6,7,8],[0,6,7,10],[2,3,5,8],[2,3,5,10],
[2,3,7,8],[2,3,7,10],[2,6,7,8],[2,6,7,10]]

• Use las combinaciones para eliminar los valores de las copias de la secuencia (vea Salida del fragmento de código).

2. Eliminar una lista desordenada de valores

Si la lista de valores a eliminar no es necesariamente una subsecuencia de la secuencia principal, y los valores se pueden eliminar en cualquier orden, se puede utilizar el mismo método que el anterior, con una relajación de las reglas de conexión cruzada:

Eliminar conexiones cruzadas de la lista de posiciones y evitar las conexiones cruzadas al generar las combinaciones solo debe hacerse para valores idénticos.

En este ejemplo, solo se eliminan las conexiones cruzadas para los valores duplicados 1; primero de izquierda a derecha:

y luego de derecha a izquierda:

lo que resulta en este gráfico simplificado, con las conexiones problemáticas cruzadas para el valor 1 eliminado, y las conexiones cruzadas para los valores 2 y 3 restantes:

A continuación se muestra un ejemplo de código adaptado de la versión para subsecuencias; solo se cambian unas pocas líneas en el código, como se indica con los comentarios (y también utilicé un método diferente para eliminar los valores de la secuencia). La lista de valores que se eliminarán se ordena al inicio, de modo que se agrupen valores idénticos para facilitar el seguimiento de valores idénticos.

function removeSubList(seq, sub) {
sub.sort(function(a, b) {return a - b}); /* SORT SUB-LIST FIRST */
var posi = []; // list position of values in seq, then connect to positions in sub
sub.forEach(function(elem) {posi[elem] = []});
seq.forEach(function(elem, index) {if (posi[elem]) posi[elem].push(index)});
var conn = sub.map(function(elem) {return posi[elem].slice()});
for (var i = 1; i < conn.length; i++) {
if (sub[i - 1] != sub[i]) continue; /* SKIP FOR NON-IDENTICAL VALUES */
var left = conn[i - 1][0];
while (conn[i][0] <= left) {
conn[i].shift(); // remove crossed connection left-to-right
}
}
for (var i = conn.length - 2; i >= 0; i--) {
if (sub[i] != sub[i + 1]) continue; /* SKIP FOR NON-IDENTICAL VALUES */
var right = conn[i + 1][conn[i + 1].length - 1];
while (conn[i][conn[i].length - 1] >= right) {
conn[i].pop(); // remove crossed connection right-to-left
}
}
var combinations = [], result = [];
combine(0, -1, []); // initiate recursion to find combinations
for (var i = 0; i < combinations.length; i++) {
var s = seq.slice(); // create copy of seq and delete values
combinations[i].forEach(function(elem) {delete s[elem]});
result[i] = s.filter(function(elem) {return elem != undefined});
}
return result;
function combine(step, prev, comb) { // generate combinations using recursion
for (var i = 0; i < conn[step].length; i++) {
var curr = conn[step][i];
if (prev >= curr && seq[prev] == seq[curr]) continue; /* SKIP FOR NIV */
if (step + 1 == conn.length) combinations.push(comb.concat([curr]));
else combine(step + 1, curr, comb.concat([curr]));
}
}
}
var result = removeSubList([1,5,1,3,4,2,3,2,1,3,1,2], [1,3,1,2,1]);
for (var i in result) document.write(result[i] + "<br>");

Answer 5

Para determinar todas las formas en que se puede eliminar un grupo de valores (llamemos a este grupo de needles ) de una secuencia (llamada haystack ), haga lo siguiente:

1. Cuente cuántas veces tiene que quitar cada needle (llamemos a esto cuenta k ). Esto puede ser determinado por un solo pase sobre las needles .
2. Encuentra todas las ubicaciones de cada needle que se eliminará en el haystack . Esto puede ser determinado por un solo pase sobre el haystack .
3. Genere todas las formas posibles en que puede eliminar cada needle individual k veces de las ubicaciones encontradas. Esta es una enumeración estándar de k- combinaciones y su complejidad de tiempo no es polinomial.
4. Genere todas las formas posibles en que puede combinar las posibilidades de eliminación de cada needle individual. Este es un producto cartesiano n estándar y su complejidad de tiempo tampoco es polinomial.
5. Para cada forma encontrada, filtra los elementos relevantes del haystack .

La siguiente es una implementación de ECMAScript 2016 de este enfoque:

function* removalCombinations(haystack, needles) {
// Comments walk through sample input of haystack = [1,2,1,3,1,4,4] and needles = [1,4,4]
// How many of each needle there are, e.g.,
// needleCounts = { 1 => 1, 4 => 2 }
let needleCounts = elementCounts(needles);
// Where each needle is located, e.g.,
// needleIndexes = { 1 => [ 0, 2, 4 ], 4 => [ 5, 6 ] }
let needleIndexes = findIndices(needleCounts.keys(), haystack.entries());
// The possible indices to be removed for a particular needle, e.g.,
// indexCombinations = [ [ [ 0 ], [ 2 ], [ 4 ] ], [ [ 5, 6 ] ] ]
var indexCombinations = [];
for (let [needle, indexes] of needleIndexes) {
indexCombinations.push(Array.from(generateCombinations(indexes, needleCounts.get(needle))));
}
// All the ways that the possible index removals can be fully combined together, e.g.,
// fullRemovalCombinations = [ [ 0, 5, 6 ], [ 2, 5, 6 ], [ 4, 5, 6 ] ]
let fullRemovalCombinations = cartesianProductOf(indexCombinations);
// For every possible index removal combination,
// filter those indices from the original haystack, e.g.,
// yielded values = [ [ 2, 1, 3, 1 ], [ 1, 2, 3, 1 ], [ 1, 2, 1, 3 ] ]
for (let indicesToFilter of fullRemovalCombinations) {
indicesToFilter = new Set(indicesToFilter);
yield haystack.filter((_, index) => !indicesToFilter.has(index))
}
// Calculates how many there are of each element.
function elementCounts(iterable) {
let counts = new Map();
for (let el of iterable) {
counts.set(el, counts.get(el) + 1 || 1);
}
return counts;
}
// Finds the indices of where each target occurs within iterable.
function findIndices(targets, entries) {
let indices = new Map();
for (let el of targets) {
indices.set(el, []);
}
for (let [index, value] of entries) {
if (indices.has(value)) {
indices.get(value).push(index);
}
}
return indices;
}
// Generates all possible combinations of choosing k elements from arr.
function* generateCombinations(arr, k) {
function* doGenerateCombinations(offset, combo) {
if (combo.length == k) {
yield combo;
} else {
let len = arr.length;
for (let i = offset; i < len; i++) {
yield * doGenerateCombinations(i + 1, combo.concat(arr[i]));
}
}
}
yield* doGenerateCombinations(0, []);
}
// Given an array of arrays, generates all ways the elements can be combined together,
// when taking a single element from each array.
function* cartesianProductOf(arrays) {
function* doCartesianProductOf(i, prod) {
if (i == arrays.length) {
yield prod;
} else {
for (let j = 0; j < arrays[i].length; j++) {
yield* doCartesianProductOf(i + 1, prod.concat(arrays[i][j]));
}
}
}
yield* doCartesianProductOf(0, []);
}
}
console.log(JSON.stringify(Array.from(removalCombinations([1, 2, 1, 3, 1, 4, 4], [1, 4, 4]))));
console.log(JSON.stringify(Array.from(removalCombinations([8, 6, 4, 4], [6, 4, 8]))));

Answer 6

(Consulte también mis otras dos respuestas a continuación, para combinaciones de conjuntos múltiples ordenadas y no ordenadas).

Para evitar "callejones sin salida" en una recursión, cree combinaciones de índices hash. Por ejemplo,

[1,2,1,3,1,4,4] / [1,3]
Hash = {1: [0,2,4], 3: [3]} // for repeated elements in the to-be-removed array,
// you could reserve the first element of the index array
Use the multi-set combination algorithm of your choice to make combinations from the
hashed indexes, like [0,3], [2,3], etc.; and accumulate results without the corresponding elements.

Answer 7

Aquí hay una solución que usa una función reiterativa para reducir los valores en pasos. Esta función no devolverá soluciones si no todos los valores de los valores que se necesitan eliminar están presentes en la matriz de inicio.

// Algorithm to strip values from an array
// Note, if not all elements of the stripValues array are found this function will return no solutions
function stripValues(startingValues, stripValues) {
let solutions = []
searchForSolutions(startingValues, stripValues, solutions, [])
return solutions
}
function searchForSolutions(startingValues, stripValues, solvedSolutions, possibleSolution) {
// If there are values to remove
if(stripValues.length > 0) {
// Copy the values of any possible solution to avoid tampering
let newPossibleSolution = []
possibleSolution.forEach((value) => {
newPossibleSolution.push(value)
})
// Loop through the starting values looking for an instance of the first remaining value to strip
for(i = 0; i < startingValues.length; i++) {
if(startingValues[i] == stripValues[0]) {
// The value was found, so reduce the arrays and look for the next element to remove
let remainingStripValues = []
stripValues.forEach((value, index) => {
if(index > 0) {
remainingStripValues.push(value)
}
})
let remainingValues = []
for(j = i + 1; j< startingValues.length; j++) {
remainingValues.push(startingValues[j])
}
// Reiterate the search
searchForSolutions(remainingValues, remainingStripValues, solvedSolutions, newPossibleSolution)
}
// Whether or not the value was found we want to continue finding permutations
newPossibleSolution.push(startingValues[i])
}
} else {
//There are no remaining values to search for, so we have found a solution
for(i = 0; i < startingValues.length; i++) {
newPossibleSolution.push(startingValues[i]);
}
solvedSolutions.push(newPossibleSolution)
}
}

Answer 8

Básicamente, esta propuesta crea un mapa con los elementos buscados para eliminar, contarlos, verifica si la longitud de los mismos elementos es la misma que en el dado, y luego ponerlo en el conjunto common . Todos los demás se usan para construir una combinación y luego para construir un producto cruzado.

Al final, se filtran todos los valores que se encuentran en el producto cruzado o en el campo común.

function remove(sequence, sub) {
var count = new Map,
distribute = [],
common = [];
sub.forEach((a, i) => {
var o = count.get(a)
if (!o) {
o = { sub: 0, pos: [] };
count.set(a, o);
}
o.sub++;
});
sequence.forEach((a, i) => {
var o = count.get(a);
o && o.pos.push(i);
});
count.forEach((v, k) => {
if (v.pos.length > v.sub) {
distribute.push({ value: k, pos: v.pos, count: v.sub });
} else {
common.push(k);
}
});
return crossProduct(distribute.map(a => combination(a.pos, a.count))).
map(a =>
sequence.filter((b, i) => a.indexOf(i) === -1 && common.indexOf(b) === -1));
}
console.log(remove([1, 2, 1, 3, 1, 4, 4], [1, 4, 4])); // [ [2,1,3,1], [1,2,3,1], [1,2,1,3] ]
console.log(remove([1, 2, 1, 3, 1, 4, 4], [1, 1])); // [ [2,3,1,4,4], [1,2,3,4,4], [2,1,3,4,4] ]
console.log(remove([1, 2, , 5, 1, 3, 5, 1, 4, 4, 5], [1, 4, 4, 5]));
function crossProduct(array) {
function c(part, index) {
array[index].forEach(a => {
var p = part.concat(a);
if (p.length === array.length) {
result.push(p);
return;
}
c(p, index + 1);
});
}
var result = [];
if (array.length === 1) { return array[0]; }
c([], 0);
return result;
}
function combination(array, size) {
function c(part, start) {
var i, l, p;
for (i = start, l = array.length + part.length + 1 - size; i < l; i++) {
p = part.slice();
p.push(array[i]);
p.length < size ? c(p, i + 1) : result.push(p);
}
}
var result = [];
c([], 0);
return result;
}

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 9

Si desea enumerar combinaciones desordenadas de un conjunto de elementos múltiples, puede hacer exactamente eso:

Registre las posiciones en la matriz de los elementos en el conjunto múltiple; enumera todas las combinaciones de choose(indexes,multiplicity) .

Código de JavaScript:

// straighforward choose(n,r) combinations
function choose(ns,r){
if (r > ns.length) return [];
var res = [];
function _choose(i,_res){
if (_res.length == r){
res.push(_res);
return;
} else if (_res.length + ns.length - i == r){
_res = _res.concat(ns.slice(i));
res.push(_res);
return
}
var temp = _res.slice();
temp.push(ns[i]);
_choose(i + 1,temp);
_choose(i + 1,_res);
}
_choose(0,[]);
return res;
}
// function to collect an array without specified indexes
function remove(arr,indexSet){
var _arr = [];
arr.forEach(function(v,i){ if (!indexSet.has(i)) _arr.push(arr[i]); });
return _arr;
}
// main function
// the multiset is formatted as {element: [multiplicity,indexes]}
function removeAllCombs(arr,multiset){
var res = [];
// record the positions of multiset elements in the array
arr.forEach(function(v,i){
if (multiset[v]) multiset[v][1].push(i);
});
var keys = Object.keys(multiset);
function enumerate(i,accum){
if (i == keys.length){
res.push(remove(arr,new Set(accum)));
return;
}
var combs = choose(multiset[keys[i]][1],multiset[keys[i]][0]);
for (let j in combs){
var _accum = accum.slice();
_accum = _accum.concat(combs[j]);
enumerate(i + 1,_accum);
}
}
enumerate(0,[]);
return res;
}
console.log(JSON.stringify(
removeAllCombs([1,2,1,3,1,4,4],{1: [1,[]], 4: [2,[]]})
));

Answer 10

(Esta respuesta también está disponible aquí: ¿Cómo puedo determinar todas las formas posibles en que se puede eliminar una subsecuencia de una secuencia? )

Esta es una respuesta para combinaciones ordenadas de conjuntos múltiples, que parece similar a enumerar subsecuencias coincidentes en la matriz más grande.

Primero, ordene que su conjunto sea eliminado en el mismo orden de aparición que en la matriz principal (tiempo O(n) con hash), luego proceda con el algoritmo siguiente.

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 ejemplo 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 definición de 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''])));