Checking intersection of arrays on javascript - how?

Question

There is a certain interface where the Russian alphabet is divided into parts (alphabetic groups of letters):

There can be any number of such groups, for this there is a button + add a group

It is necessary to implement the functionality of checking for the intersection of ranges of alphabetic groups, i.e. The screenshot above shows a valid breakdown example, but this one is already wrong:

all because in the first group we have a range of letters from A to K, and in the second from the same K to T, so the second group intersects with the first letter K

How to implement such an intersection checking algorithm in JavaScript?

In this case, you can not check the arrays, it is enough to take the maximum and minimum elements of the group and check them with the same elements in the neighboring group through > and < .
if you are about option inside select, then you can store numbers there as value - the keys of the array from which values are built for select
What should be issued on the following partition - N-Z, AM ?
These are not intersecting ranges, but are not in alphabetical order.

Accepted Answer · 2015-12-22T14:33:08

For your case it is not necessary to check the full occurrence, it is enough to take the maximum and minimum elements of the group and check them with the same elements in the neighboring group through > and < . In this case, when using <select> , you already have these values initially and you just have to go over them and check.

 var validation = function(selectArray){ for(var i=1; i<selectArray.length; i++) { if(selectArray[i].value <= selectArray[i-1].value) return false; } return true; } document.getElementById("process").onclick = function() { var selectArray = document.getElementsByTagName("select"); document.getElementById("result").innerHTML = validation(selectArray); }

  <div id="select"> <select> <option>А</option> <option>Б</option> <option>В</option> <option>Г</option> </select> <select> <option>А</option> <option selected>Б</option> <option>В</option> <option>Г</option> </select> <select> <option>А</option> <option>Б</option> <option selected>В</option> <option>Г</option> </select> <select> <option>А</option> <option>Б</option> <option>В</option> <option selected>Г</option> </select> </div> <div id="result">result</div> <button id="process">Проверить</button>

There are no built-in tools in the JavaScript language, but there is a way to determine whether an element is in the array through indexOf, which simplifies the task. The easiest way to check the entry of one array into another and the elements of this entry are:

 function Intersect(left, right) { return left.filter(function(el){ return right.indexOf(el) != -1; }); }

This method may not be the fastest, for very large arrays on the Internet are laid out more effective methods.

CG, AB — two non-intersecting ranges, but your code discards it
The code is sharpened exclusively for this particular case, which does not imply the wrong order of incoming groups in the markup or groups of one character.
The Russian alphabet is clearly indicated in the question, where is “EOZH”, and logically it should be Е <Ё <Ж , but in reality E <Е and Ж < Е , which does not allow to compare letters with the operator <=
@MiKeBu, I say that I did not set myself the goal of writing a universal version.
If it is necessary to solve the problem in a more universal way, then my answer is certainly not suitable, which was originally stated.
If you need a universal solution, you will have to come up with something else, like you did.

Answer 2 · 2016-01-01T15:44:04

Here is my implementation.

Works with arbitrary sequences of characters , their order ("alphabet") set in the variable alphabet .

As a result, the code is capable of processing Russian E , Ukrainian Є and Ї , as well as other characters of national alphabets, which are located separately in the coding table and, when comparing, give an unpredictable result.

Under your task, you only need to collect the borders of the intervals from the page and send them for processing in the form [начало1,конец1, ... ,началоN,конецN] , examples will be found below in the tests.

 function checkIntersect(groups){ groups=groups.map(function(e){return e.toLowerCase();}); //alphabet - порядок символов алфавита var alphabet="абвгдеёжзийклмнопрстуфхцчшщъыьэюя".toLowerCase(), correct=true; function diapazone(a,b){ //ищем граничные символы и подстроку между ними var p1=alphabet.indexOf(a), p2=alphabet.indexOf(b), min=p1<p2 ? p1 : p2, max=p1<p2 ? p2 : p1, substr=alphabet.substring(min,max+1); if(p1<0 || p2<0 || substr.indexOf('-')>=0) return false; //не найден символ или внутри уже меняли - косяк alphabet=alphabet.replace(substr,'-'); //ставим метку о замене return true; } for(var i=0; i<groups.length; i+=2)//перебираем диапазоны correct = correct && diapazone(groups[i],groups[i+1]); return correct; } /*************Тесты*************/ function test(c){ var res=checkIntersect(c); document.write(c[0]+"-"+c[1]+","+c[2]+"-"+c[3]+": "+res+"<br>"); } test(["а","а","б","я"])//однобуквенный интервал test(["а","м","н","я"])//типичные интервалы test(["н","я","а","м"])//обратный порядок последовательностей test(["я","н","м","а"])//развернутые последовательности test(["а","е","ё","я"])//хитрая буква Ё test(["а","я","м","н"])//включение одного интервала в другой test(["а","н","м","я"])//пересечение двух интервалов test(["а","м","н","z"])//не-алфавитные символы

Why in the code on the constant string toLowerCase () and the variable correct?
correct is a result variable, accumulating errors there with the help of "logical and" ( && in code).
.toLowerCase() for the alphabet is a formality, since the arguments are also reduced to lower case.
Good answer, let me have a little more support then)) 1. On the constant string toLowerCase() superfluous.
2. The variable variable is meaningless, if diapazone returns false , the variable will not change anymore, a further pass does not make sense.
You can safely exit checkIntersect with return false skipping all other checks and save time.
3. micro-optimization: substr = p1 < p2 ? alphabet.substring(p1, p2+1) : alphabet.substring(p2, p1+1);
substr = p1 < p2 ? alphabet.substring(p1, p2+1) : alphabet.substring(p2, p1+1);
Thank you) Regarding correct : its sole purpose is the talking variable name.

Checking intersection of arrays on javascript - how?

2 answers 2

More articles: