JavaScript: вычитание диапазонов чисел

Я пытаюсь написать JS-функцию, которая имеет два параметра: include и exclude, каждый из которых представляет собой массив объектов {X, Y}, который представляет диапазон чисел от X до Y, оба включены.

Вывод - это вычитание всех диапазонов в include со всеми диапазонами в exclude.

Например:

include = [ {1,7}, {9,10}, {12,14} ]
exclude = [ {4,5}, {11,20} ]
output = [ {1,3}, {6,7}, {9,10} ]
  • {4,5} разбил {1,7} на два объекта диапазона: {1,3} и {6,7}
  • {9,10} не было затронуто
  • {12,14} полностью удалено
6 ответов

Здесь ответ, который работает с фракциями, и это не просто грубое форсирование. Я добавил комментарии, чтобы объяснить, как это работает. Это может показаться большим, предпосылка проста:

  • создайте метод p1_excluding_p2, который принимает точки p1 и p2 и возвращает массив точек, которые существуют после выполнения p1 - p2

  • создайте метод points_excluding_p2, который выполняет ТОЧНУЮ ту же операцию, что и выше, но на этот раз позволяет нам передать массив points и вернуть массив точек, которые существуют после вычитания p2 из всех точки в нашем массиве, так что теперь мы имеем (points) - p2

  • создайте метод p1_excluding_all, который принимает противоположный вход, как указано выше. На этот раз примите одну точку p1 и множество точек исключения и верните массив точек, оставшихся после вычитания всех точек исключения. Это на самом деле очень легко создать сейчас. Мы просто начинаем с [p1] и первой точки исключения (exclusion1) и передаем ее в points_excluding_p2. Мы берем массив, который возвращается (который будет p1 - exclusion1), и передайте его в points_excluding_p2 только на этот раз с помощью exclusion2. Мы продолжаем этот процесс, пока не исключим каждую точку исключения, и мы останемся с массивом p1 - (all exclusion points)

  • теперь, когда у нас есть возможность выполнить p1 - (all exclusion points), это всего лишь вопрос циклизации всех наших точек и вызов p1_excluding_all, и мы остаемся с массивом каждой точки, вычитаем каждую точку исключения. Мы запускаем наши результаты с помощью remove_duplicates, если у нас есть какие-то повторяющиеся записи, и что об этом.

Код:

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, i.e. 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, i.e. 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);

который возвращает:

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


Правило для целочисленной арифметики для вычитания двух наборов X,Y равно

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

но это не то, что вы хотите, как кажется.

Вы можете принять упорядоченные множества в вашем примере, который позволяет вам установить любое вхождение x==y в качестве произвольного значения в массиве JavaScript и использовать его для разделения. Но вам это не нужно.

Установленная разность {1...7}\{4...5} расширяется до {1,2,3,4,5,6,7}\{4,5}. Как вы можете легко заметить, вычитание с правилом заданной арифметики оставило бы {1,2,3,0,0,6,7} и с нормальным вычитанием (символ \) вы получите {1,2,3,6,7}.

Установленная разность {12...14}\{11...20} расширяется до {12,13,14}\{11,12,13,14,15,16,17,18,19,20}; заданный арифм. разница равна {-11,0,0,0, -15, -16,..., - 20}, но нормальное сложение-вычитание оставляет пустое множество {}.

Обработка операций с пустым множеством эквивалентна обычной арифметике {x}-{}={x} и {}-{x} = {-x} для правил арифметического набора и {x}\{}={x}, {}\{x}= {} с обычными правилами

Итак, что вы должны использовать здесь, в соответствии с вашим примером, являются нормальными правилами набора. Нет необходимости расширять множества, их можно считать плотными.

Вы можете использовать относительные различия (вы можете называть их расстояниями).

При {1...7}\{4...5} первый запуск мал, тогда второй старт и первый конец больше второго конца, что привело к двум различным наборам.

При {12...14}\{11...20} первый старт больше второго запуска, а первый конец ниже, чем второй, что привело к пустующему набору.

В третьем примере используется правило с пустым множеством.

Вам нужен фрагмент примера?


ПРИМЕЧАНИЕ: include = [ {1,7}, {9,10}, {12,14} ] недействителен javascript, поэтому я предположил, что вы передаете массивы массивов, а именно:

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

Метод грубой силы (решение может быть не самым красноречивым):

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/


Вы можете использовать алгоритм развертки. Для каждого номера сохраняйте то, что он представляет (начало и конец, включение и исключение). Затем поместите все число в массив и отсортируйте его. Затем итеративно удалите элементы из массива и выполните соответствующую операцию.

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

поддерживать переменные include и exclude увеличивать их с началом соответствующих элементов и уменьшать их при получении конечных элементов. Согласно значению include и exclude вы можете определить, что вы должны начать новый диапазон, закрыть диапазон открытия или ничего не делать.

Этот алгоритм работает в линейном времени O (n).


Здесь рабочее решение, которое обрабатывает 4 возможных сценария перекрытия для диапазона исключения.

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++){ 4="" var="" inc="include[i];" overlap="false;" for="" (var="" x="0;x<exclude.length;x++" ){="" exc="exclude[x];" 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);
</include.length;i++){>


Возможно, мы сможем сделать его несколько более эффективным, объединив помеченные интервалы в один отсортированный список:

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] ];

Затем, перемещая список и для любого исключенного интервала, обновляйте любые окружающие промежутки.

licensed under cc by-sa 3.0 with attribution.