JavaScript: restar ranges de numbers

Estoy intentando escribir una function JS que tiene dos parameters, include y excluir, cada uno una matriz de objects {X, Y} que representa un range de numbers de X a Y, ambos incluidos.

La salida es la resta de todos los ranges incluidos con todos los ranges en exclude.

Por ejemplo:

include = [ {1,7}, {9,10}, {12,14} ] exclude = [ {4,5}, {11,20} ] output = [ {1,3}, {6,7}, {9,10} ] 
  • {4,5} rompió {1,7} en dos objects de range: {1,3} y {6,7}
  • {9,10} no se vio afectado
  • {12,14} fue eliminado por completo

6 Solutions collect form web for “JavaScript: restar ranges de numbers”

La regla para la aritmética de sets integers para la resta de dos sets X,Y es

 X − Y := {x − y | x ∈ X, y ∈ Y } 

pero eso no es lo que quieres, como parece.

Puede asumir sets orderados en su ejemplo que le permiten establecer cada ocurrencia de x==y como un valor arbitrario en una matriz de JavaScript y usar eso para dividir allí. Pero no necesitas eso.

La diferencia establecida {1...7}\{4...5} se expande a {1,2,3,4,5,6,7}\{4,5} . Como puede ver fácilmente, una resta con la regla de la aritmética establecida dejaría {1,2,3,0,0,6,7} y con la resta establecida normal (símbolo \ ) se obtiene {1,2,3,6,7} .

La diferencia establecida {12...14}\{11...20} se expande a {12,13,14}\{11,12,13,14,15,16,17,18,19,20} ; el aritm establecido. la diferencia es {-11,0,0,0, -15, -16, …, – 20} pero la resta-resta normal deja el set vacío {} .

El event handling operaciones con el set vacío es equivalente a la aritmética normal {x}-{}={x} y {}-{x} = {-x} para las reglas de set aritmético y {x}\{}={x} , {}\{x}= {} con reglas normales

Entonces, lo que tienes que usar aquí, de acuerdo con tu ejemplo, son las reglas establecidas normales. No es necesario expandir los sets; se puede suponer que son densos.

Puede usar diferencias relativas (puede llamarlas distancias).

Con {1...7}\{4...5} el primer inicio es pequeño, luego el segundo comienza y el primero es mayor, el segundo, lo que da como resultado dos sets diferentes.

Con {12...14}\{11...20} el primer inicio es mayor que el segundo inicio y el primer final es más bajo que el segundo extremo, que dio como resultado un set vacío.

El tercer ejemplo hace uso de la regla de set vacío.

¿Necesitas un fragment de ejemplo?

Aquí hay una respuesta que funciona con fracciones y que no es solo el forzamiento bruto. He agregado comentarios para explicar cómo funciona. Puede parecer grande, la premisa es simple:

  1. crear un método p1_excluding_p2 que acepte los puntos p1 y p2 y los retornos de un set de puntos que existen después de hacer p1 - p2

  2. crea un método points_excluding_p2 que realiza la misma operación EXACTA que antes, pero esta vez nos permite pasar una matriz de points y devolver una matriz de puntos que existen después de restar p2 de todos los puntos de nuestra matriz, por lo que ahora tenemos (points) - p2

  3. crea un método p1_excluding_all que toma la input opuesta como se p1_excluding_all anteriormente. Esta vez, acepte un punto p1 y muchos puntos de exclusión, y devuelva la matriz de puntos restantes después de restar todos los puntos de exclusión. Esto es realmente muy fácil de crear ahora. Simplemente comenzamos con [p1] y el primer punto de exclusion1 ( exclusion1 ) y alimentamos esto en points_excluding_p2 . Tomamos la matriz que vuelve (que será p1 - exclusion1 ) y la points_excluding_p2 en points_excluding_p2 solo esta vez con exclusion2 . Continuamos este process hasta que hayamos excluido todos los puntos de exclusión, y nos queda una matriz de p1 - (all exclusion points)

  4. ahora que tenemos el poder de ejecutar p1 - (all exclusion points) , solo es cuestión de recorrer todos nuestros puntos y llamar a p1_excluding_all , y nos queda una matriz de cada punto que resta cada punto de exclusión. remove_duplicates nuestros resultados a través de remove_duplicates caso de que tengamos inputs duplicadas, y eso es todo.

El código:

 var include = [ [1,7], [9,10], [12,14] ] var exclude = [ [4,5], [11,20] ] /* This method is just a small helper method that takes an array * and returns a new array with duplicates removed */ function remove_duplicates(arr) { var lookup = {}; var results = []; for(var i = 0; i < arr.length; i++) { var el = arr[i]; var key = el.toString(); if(lookup[key]) continue; lookup[key] = 1; results.push(el); } return results; } /* This method takes 2 points p1 and p2 and returns an array of * points with the range of p2 removed, ie p1 = [1,7] * p2 = [4,5] returned = [[1,3],[6,7]] */ function p1_excluding_p2(p1, p2) { if(p1[1] < p2[0]) return [p1]; // line p1 finishes before the exclusion line p2 if(p1[0] > p2[1]) return [p1]; // line p1 starts after exclusion line p1 var lines = []; // calculate p1 before p2 starts var line1 = [ p1[0], Math.min(p1[1], p2[0]-1) ]; if(line1[0] < line1[1]) lines.push(line1); // calculate p1 after p2 ends var line2 = [ p2[1]+1, p1[1] ]; if(line2[0] < line2[1]) lines.push(line2); // these contain the lines we calculated above return lines; } /* this performs the exact same operation as above, only it allows you to pass * multiple points (but still just 1 exclusion point) and returns results * in an identical format as above, ie points = [[1,7],[0,1]] * p2 = [4,5] returned = [[0,1],[1,3],[6,7]] */ function points_excluding_p2(points, p2) { var results = []; for(var i = 0; i < points.length; i++) { var lines = p1_excluding_p2(points[i], p2); results.push.apply(results, lines); // append the array lines to the array results } return results; } /* this method performs the same operation only this time it takes one point * and multiple exclusion points and returns an array of the results. * this is the important method of: given 1 point and many * exclusion points, return the remaining new ranges */ function p1_excluding_all(p1, excluded_pts) { var checking = [p1]; var points_leftover = []; for(var i = 0; i < exclude.length; i++) { checking = points_excluding_p2(checking, exclude[i]); } return remove_duplicates(checking); } /* now that we have a method that we can feed a point and an array of exclusion * points, its just a simple matter of throwing all our points into this * method, then at the end remove duplicate results for good measure */ var results = []; for(var i = 0; i < include.length; i++) { var lines = p1_excluding_all(include[i], exclude); results.push.apply(results, lines); // append the array lines to the array results } results = remove_duplicates(results); console.log(results); 

que devuelve:

 [[1,3],[6,7],[9,10]] 

NOTA: include = [ {1,7}, {9,10}, {12,14} ] no es javascript válido, por lo que asumí que pasa en matrices de matrices en lugar de, por ejemplo:

  include = [ [1,7], [9,10], [12,14] ] 

Método de fuerza bruta (una solución, puede no ser la más eloquent):

 function solve_range(include, exclude) { numbers = []; include.forEach(function (range) { for (i = range[0]; i <= range[1]; i++) { numbers[i] = true; } }); exclude.forEach(function (range) { for (i = range[0]; i <= range[1]; i++) { numbers[i] = false; } }); contiguous_start = null; results = []; for (i = 0; i < numbers.length; i++) { if (numbers[i] === true) { if (contiguous_start == null) { contiguous_start = i; } } else { if (contiguous_start !== null) { results[results.length] = [contiguous_start, i - 1]; } contiguous_start = null; } } return results; } var include = [ [1, 7], [9, 10], [12, 14] ]; var exclude = [ [4, 5], [11, 20] ]; var output = solve_range(include, exclude); 

https://jsfiddle.net/dwyk631d/2/

Aquí hay una solución de trabajo que maneja los 4 posibles escenarios de superposition para un range de exclusión.

 var include = [{from:1, to: 7},{from: 9, to: 10},{from: 12, to: 14}]; var exclude = [{from:4, to: 5}, {from: 11, to: 20}]; //result: {1,3}, {6,7}, {9,10} var resultList = []; for (var i=0;i<include.length;i++){ var inc = include[i]; var overlap = false; for (var x=0;x<exclude.length;x++ ){ var exc = exclude[x]; //4 scenarios to handle if (exc.from >= inc.from && exc.to <= inc.to){ //include swallows exclude - break in two resultList.push({from: inc.from, to: exc.from - 1}); resultList.push({from: exc.to + 1, to: inc.to}); overlap = true; }else if (exc.from <= inc.from && exc.to >= inc.to){ //exclude swallows include - exclude entire range overlap = true; break; }else if (exc.from <= inc.from && exc.to <= inc.to && exc.to >= inc.from){ //exclusion overlaps on left resultList.push({from: exc.to, to: inc.to}); overlap = true; }else if (exc.from >= inc.from && exc.to >= inc.to && exc.from <= inc.to){ //exclusion overlaps on right resultList.push({from: inc.from, to: exc.from - 1}); overlap = true; } } if (!overlap){ //no exclusion ranges touch the inclusion range resultList.push(inc); } } console.log(resultList); 

Puede usar el algorithm de línea de barrido. Para cada número, guarde lo que representa (inicio y fin, inclusión y exclusión). Luego coloque todos los numbers en una matriz y oriéntelos. A continuación, elimine iterativamente elementos de la matriz y realice la operación adecuada.

 include_list = [[1,7]] exclude_list = [[4,5]] (1,start,inclusion),(4,start,exclusion),(5,end,exclusion),(7,end,inclusion) include = 0 exclude = 0 cur_element = (1,start,inclusion) -> include = 1, has_open_range = 1, range_start = 1 // we start a new range starting at 1 cur_element = (4,start,exclusion) -> exclude = 1, has_open_range = 0, result.append ( [1,4] ) // we close the open range and add range to result cur_element = (5,end,exclusion) -> exclude = 0, has_open_range = 1, range_start = 5 // because include was 1 and exclude become 0 we must create a new range starting at 5 cur_element = (7,end,inclusion) -> include = 0, has_open_range = 0, result.append([5,7]) // include became zero so we must close the current open range so we add [5,7] to result 

mantenga las variables include y exclude increment them con el inicio de los elementos respectivos y disminuya al recibir los elementos finales. De acuerdo con el valor de include y exclude , puede determinar si debe comenzar un nuevo range, cerrar el range abierto o no hacer nada en absoluto.

Este algorithm se ejecuta en time lineal O (n).

Tal vez podamos hacerlo un poco más eficiente al combinar los intervalos labeldos en una list orderada:

 include = [ {1,7}, {9,10}, {12,14} ] exclude = [ {4,5}, {11,20} ] merged = [ [1,7,0], [4,5,1], [9,10,0], [11,20,1], [12,14,0] ]; 

Luego, recorra la list y, para cualquier intervalo excluido, actualice los intervalos afectados circundantes.

  • Encontrar numbers con un valor similar en el set
  • Configuración basada en la localización en Javascript, ordera las letras acentuadas y otras variantes de una manera pnetworkingefinida
  • javascript - encuentra el subset que da la sum máxima por debajo de un cierto límite (sum de subsets)
  • ¿Cómo se implementa document.querySelector?
  • ¿Cuál es el algorithm de levenshtein más rápido para uso frecuente?
  • Cambiando O (n ^ 3) a O (n ^ 2) en JavaScript
  • Camino completo de un object json
  • Implementando la function de inserción
  • Algoritmo para dividir palabras random en grupos de longitud definida
  • Uniformemente arreglando puntos en una esfera usando Rejas de Fibonacci
  • ¿Cómo clasifico una matriz de objects según el order de otra matriz?
  • ¿Hay alguna biblioteca para editar de forma eficiente cadenas grandes en Javascript?
  • ¿Puede una string tener un palíndromo? ¿Hay alguna forma mejor de hacerlo?
  • Javascript tiene muchos buenos JS marco (como Node.js AngularJS Vue.js React.js) es el mejor lenguaje de script.