Добрый день, коллеги и просто форумчане.

Суть задачи вот в чем. Есть диапазоны DEF-кодов операторов связи. Начало диапазона и конец. Необходимо найти паттерны вхождения в данный диапазон минимальной длины.
К примеру:
От: 79232400000
До: 79232499999
Здесь все просто, наименьший паттерн будет 792324. По этому паттерну, бизнес логика другого приложения ищет вхождения заданного номера к определенному оператору связи.
То есть ищут, к примеру, 79232465789 и он попадет под этот паттерн.
пример сложнее:
79251000000
79252999999
вот тут уже паттернов будет два: [79251, 79252]
ну и самый трэш в Российских кодах:
79260000199
79280299998
я даже все паттерны сейчас не напишу... их очень много.

Алгоритм не могу придумать, чтобы обойти все диапазоны за реальное время(можно и перебором в нереальное, что не хочется).

Мой миелофон показывает, что тебе нужно найти диапазон, к которому относится число, из множества непересекающихся диапазонов. К сожалению, миелофон не может определить, допустимо ли в данном случае использование реляционной БД. Если допустимо, то задача решается тривиальным, очевидным и эффективным способом. Если же нет, то хотелось бы узнать, какие технологии и языки программирования допустимы.

А вот мой миелофон подсказывает, что я уже верно описал задачу. Если бы была задача только найти вхождение в диапазон, то это уже есть. Суть в нахождении префиксов, входящих в диапазон.
http://stackoverflow.com/questions/1016562...-to-prefix-list

UnderGreen, Тоесть сначало было придумано "решение", а потом остается только волоса рвать, что оно не подходит для реальной жизни?

Нужно ответить на вопросы:
При чем тут паттерны? Что это такое? Зачем они? 

Телефоны, записанные 10 цифрами, хранятся как строки? Может, если хранить их как числа - само понятие "паттерн" отвалится за ненадобностью?

для
79260000199
79280299998
получается:

79260000199
792600002
...
792600009
79260001
...
79260009
7926001
...
7926009
792601
...
792609
79261
...
79269
7927
792800
792801
7928020
...
7928028
79280290
...
79280298
792802980
...
792802998
и т.д. до
79280299998

а алгоритм такой:
двигаемся от первого числа (79260000199) к концу (79280299998)
1) берем текущее число если последняя цифра 9, то это готовый шаблон, и текущее число увеличиваем на 1
2) если в последнем разряде 0, то проверяем нельзя ли его заменить на девятки, чтоб не выйти за конец
если можно, затираем эту цифру (убираем последний разряд) и идём к пункту 1
если нельзя, то пытаемся поставлять вместо последнего нуля последовательно от 1 до 9
но если не подставляется даже 1, то добавляем новый разряд нулём

3) а если в последнем разряде не 0, то идем в середину 2-го пункта где перебор до 9

как-то так

Я все никак не могу понять, зачем для телефонных номеров могут понадобиться именно текстовые шаблоны. Единственное, что приходит в голову - текстовое поле ввода в клиентском приложении, не позволяющее ввести некорректный для выбранного оператора номер. Но тогда непонятно, при чем тут "обойти все диапазоны за реальное время"? И даже в этом искуственном, притянутом за уши примере можно эффективно использовать поиск по числовым диапазонам, без всяких шаблонов.

Может, это какая-то учебная задача, и препод зачем-то требует использовать именно шаблоны?

Задача не учебная. Есть уже определенный код, старый, переписывать его нет времени у разработчиков. Функционал поиска совпадения номера телефона по префиксам в базе. Сейчас у меня задача обновить префиксы в базе.

Если бы не было старого кода, который надо переписывать. То тут было бы просто - писать в базу старт диапазона, конец диапазона и потом с ними работать как два пальца об асфальт. Можно даже бинарным деревом представить, но тут элементарно решается SQL-запросом.
Но... Мир не идеален и приходится извращаться, подстраиваясь под него.

Добавлено через 2 минуты и 30 секунд
Lipetsk, Спасибо, Ваше решение интересное, пытаюсь это разложить в код. 

Добавлено через 6 минут и 19 секунд
>> Но тогда непонятно, при чем тут "обойти все диапазоны за реальное время"?
Код приложения не работает по тому, алгоритму, который я запросил.
У меня есть таблица БД с уже имеющимися префиксами. Надо таблицу обновить. На входе я имею документ от Россвязи, в котором есть DEF/ABC код, старт диапазона, конец диапазона, Оператор, Регион. Надо эти входные данные запихнуть в таблицу, чтобы они представляли из себя префиксы.
Колоссальный оверхед по сравнению с диапазонами, но причину выше я отписал. 

Тяжелый случай. Боюсь, лучшим решением будет уволиться по собственному :(

Здесь можно использовать рекурсивную функцию, принимающую 3 параметра: общий префикс (фиксированные старшие разряды номера), начало диапазона, конец диапазона (оставшиеся разряды). Изначально общий префикс - пустая строка. Первым делом находим самый длинный общий префикс двух границ, добавляем его к переданному общему префиксу, от границ оставляем только младшие разряды (суффиксы). Например, для входных параметров (12, 34567, 34890) получается префикс 1234 и суффиксы 567 и 890. Если все разряды суффикса нижней границы нули, а верхней границы - девятки, то выводим префикс и выходим из функции.

Для определенности считаем, что суффиксы получились 3-разрядные - {a}{b}{c} для нижней границы и {x}{y}{z} для верхней. Выводим в качестве готовых префиксов номеров строки:
 префикс . {a+1}
 префикс . {a+2}
 ...
 префикс . {x-2}
 префикс . {x-1}
где точка означает конкатенацию строк.

Затем рекурсивно вызываем функцию с параметрами (префикс, {a}{b}{c}, {a}{9}{9}) и (префикс, {x}{0}{0}, {x}{y}{z}). В результате будут выведены все префиксы номеров для диапазона.

Это сообщение отредактировал(а) AVA12 - 29.11.2013, 17:17

UnderGreen, давайте всё-таки посмотрим чуть дальше. Считай, что из праздного любопытства - чтобы не так раздражало.

Вот получил ты эти свои префиксы. Допустим. Дальше - что? Где и как они будут храниться? как именно использоваться? Строго в той части, которая подконтрольна тебе.

Я вот что-то не понимаю, вроде все расписал. Хранятся в БД, мне ничего кроме как положить их в БД и не надо. По моей части более работы нет. Хранятся в виде {region, prefix, price_in, price_out, other_table_fields }.

Насчет уволиться - это я не собираюсь . Как я уже сказал, есть рабочая бизнес-логика(привет молдавским программистам). Нынешние программеры адекватные, просто времени на рефакторинг как обычно не выделяют. А данные обновлять надо время от времени(что поделать, в России телефонные префиксы меняются каждый месяц по нескольку раз). Я админ, не программист в общем, более с Erlang знаком по работе(VoIP-сервисы). А вот приходится порой делать вещи, которые к моей работе относятся как это обычно бывает:
Слушай, ну ты же программист вроде. У меня вот телевизор сломался. Починишь?

Алгоритм вычисления "паттерна" такой.

Берем нижнюю границу диапазона  Отнимаем единицу и называем паттерном все подряд совпавшие цифры сначала + еще одну 1

Для 
получится 792323999999 и 79232400000 совпадают 79232 и 4

дописываем к "паттерну" все 9-ки до получения полного номера. Если не превосходит верхнюю границу - паттерн настоящий, передвигаетмся на цифру паттерн999999 +1. Если выскочили за диапазон - профит.

Если полученное число больше верхней границы диапазона - дописываем 2 цифры числа и повторяем.

Пример для 

 1. 79260000199 и 79260000198 - "паттерн" - 79260000199, настоящий
 2. 79260000200 и 79260000199 - "паттерн" - 792600002, настоящий
 3. 79260000300 и 79260000299 - "паттерн" - 792600003, настоящий
... +  6 паттернов  792600004, 5,6,7,8,9
10. 79260001000 и 79260000999 - "паттерн" - 79260001, настоящий
... + 9 паттернов
20. 79260010000 и 79260009999 - "паттерн" - 7926001, настоящий
... + 9
30. 79260100000 и 79260099999 - "паттерн" - 792601, настоящий
31. 79260200000 и 79260199999 - "паттерн" - 792602, не подходит, так как 79260299999 выходит за диапазон, берем 7926020, настоящий
... + 8
40. 79260290000 и 79260289999 - "паттерн" - 7926029, не подходит, так как 79260299999 выходит за диапазон, берем 79260290, настоящий
... + 9
50. 79260299000 и 79260298999 - "паттерн" - 79260299, не подходит, так как 79260299999 выходит за диапазон, берем 792602990, настоящий
... + 9
60. 79260299900 и 79260299899 - "паттерн" - 792602999, не подходит, так как 79260299999 выходит за диапазон, берем 7926029990, настоящий
... + 9
70. 79260299990 и 79260299989 - "паттерн" - 7926029999, не подходит, так как 79260299999 выходит за диапазон, берем 79260299990, настоящий
... + 7
78. 79260299998 - настоящий, +1 выходим за диапазон, профит.


Это сообщение отредактировал(а) ksnk - 30.11.2013, 17:56

На работе понадобилось решить такую же задачу. 
Как программист - профан. php изучаю недавно. Код конечно не профессиональный (очень непрофессиональный). Но работает. И может кому надо.

<?php

$min = 79003450000;
$max = 79003749999;

$fp = fopen('pattern.csv', 'w+'); // тут результат

ll:
$rez = '';
$dlina = strlen($min);
$array1 = preg_split('//',$min-1); array_pop($array1); array_shift($array1);
$array2 = preg_split('//',$min); array_pop($array2); array_shift($array2);
$array3 = preg_split('//',$max); array_pop($array3); array_shift($array3);

$x=0;

ff:
$a = $array1[$x];
$b = $array2[$x];

if ($a == $b){ 
                   $rez = $rez.$a; $x++."\n"; goto ff;
                 }
$rez = $rez.$array2[$x++]; 
$tmp_rez = '';
   
switch ($dlina - strlen($rez)) {
case 0: $tmp_rez = ''; break;
case 1: $tmp_rez = '9'; break;
case 2: $tmp_rez = '99'; break;
case 3: $tmp_rez = '999'; break;
case 4: $tmp_rez = '9999'; break;
case 5: $tmp_rez = '99999'; break;
case 6: $tmp_rez = '999999'; break;
case 7: $tmp_rez = '9999999'; break;
case 8: $tmp_rez = '99999999'; break;
case 9: $tmp_rez = '999999999'; break;
case 10: $tmp_rez ='9999999999'; break;
case 11: $tmp_rez ='99999999999'; break;
}
$mmm = $rez.$tmp_rez;
echo '$rez ='.$rez."\n";
echo '$mmm ='.$mmm."\n";
echo '$tmp_rez='.$tmp_rez."\n";

if ($mmm <= $max) {
                    $min = ($rez.$tmp_rez + 1);
                    fwrite($fp, $rez."\n");   
                    if (($rez.$tmp_rez + 1) > $max) { goto stop;}
                    goto ll;
                 }

elseif ($mmm > $max) {   $min = $rez.$array3[$x+1];              
                         goto ff;
                         }
stop:
echo "результат тут pattern.csv";
?>