Проверка пересечения массивов на JavaScript - как?

176

15 апреля 2018, 23:49

Есть некий интерфейс, где происходит разбиение русского алфавита на части (алфавитные группы букв):

групп таких может быть сколько угодно, для этого есть кнопочка + добавить группу

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

всё потому что в первой группе у нас диапазон букв от А до К, а во второй от той же К до T, таким образом вторая группа пересекается с первой по букве К

Как такой алгоритм проверки пересечения реализовать на JavaScript?

Answer 1

Для вашего случая не обязательно проверять полное вхождение, достаточно взять максимальные и минимальные элементы группы и проверить их с такими же элементами в соседней группе через > и <. При этом при использовании <select> эти значения у Вас уже есть изначально и остается только пройтись по ним и проверить.

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>

Встроенных средств в языке JavaScript нет, но есть способ определить вхождение элемента в массив через indexOf что упрощает задачу. Самый просто способ проверить вхождение одного массива в другой и элементы этого вхождения:

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

Этот метод может быть не самым быстрым, для очень больших массивов в интернете выложены более эффективные методы.

Answer 2

Вот моя реализация.

Работает с произвольными последовательностями символов, их порядок ("алфавит") задаете в переменной alphabet.

Как следствие - код способен обрабатывать русское Ё, украинские Є и Ї, а также прочие символы национальных алфавитов, находящиеся отдельно в таблице кодировки и при сравнении дающие непредсказуемый результат.

Под вашу задачу потребуется лишь собрать со страницы границы интервалов и отправить их на обработку в виде[начало1,конец1, ... ,началоN,конецN], примеры найдете ниже в тестах.

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"])//не-алфавитные символы