Нужно преобразовать номерную емкость из одного формата в другой, кто может подсказать алгоритм?

Question

[Александр]

День добрый, уважаемые коллеги.
Есть задача разложить номерную емкость вида "9266070005-9266099923"
на составляющие (маски):
9266070005, 9266070006, 9266070007, 9266070008, 9266070009, 926607001, 926607002
926607003, 926607004, 926607005, 926607006, 926607007, 926607008, 926607009, 92660701, 92660702, 92660703, 92660704, 92660705, 92660706, 92660707, 92660708, 92660709, 9266071, 9266072, 9266073, 9266074, 9266075, 9266076, 9266077, 9266078
9266079, 926608, 9266091, 9266092, 9266093, 9266094, 9266095, 9266096, 9266097, 9266098, 92660991, 92660992, 92660993, 92660994, 92660995, 92660996, 92660997, 92660998, 926609990, 926609991, 9266099920, 9266099921, 9266099922, 9266099923.
Исходных диапазонов порядка 4700, но исторически сложилось, что используются емкости именно масками а не диапазонами.
Прямым перебором делать не вариант, перебором с последнего различающегося символа - тоже (в случае 9266050000-9266099999, ещё можно обойти, и сделать перебором, получив 5 масок, но это тоже не лучший вариант).
Условий исходных всего ничего:
1. Номера начального диапазона всегда в одном DEF-коде
2. Номера начального диапазона всегда из 10 цифр
3. Первый номер диапазона всегда меньше или равен последнему.
4. На выходе нужно получить минимальное количество масок, охватывающее исходный диапазон (включая первый и последний номер).
Заранее благодарен.

Comments

[romy4]

Непонятен алгоритм формирования "масок"

[Александр]

romy4:
Маска - почти регулярка, под которую подходит часть диапазона (или весь).
Например для 9266050000-9266099999:
926605
926606
926607
926608
926609
Регуляркой это выглядело бы так: 92660[5-9]\d{4}

[Антон Федорян]

Александр: так вам просто количество нужно или сами получившиеся значения?

[Александр]

Антон Федорян: Мне нужны именно значения, точнее алгоритм подбора минимального достаточного набора этих значений, исторически сложилось, что в компании оператор определяется именно по префиксу (в моей интерпретации маске), а база получаемая от МТТ идёт диапазонами.

Answer 1

[Mrrl]

Хорошая задача. На C# это бы выглядело так:

long x0=9266070005,x1=9266099923;
            long n=1;
            x1++;
            while(x0<x1) {
                if(x1-x0<n) n/=10;
                else if((x0/n)%10==0 && x1-x0>=10*n) n*=10;
                else{
                    Console.Write("{0}, ",x0/n);
                    x0+=n;
                }
            }

Можно ли это хорошо переписать на PHP, не знаю.

Comments

[Александр]

Спасибо. Ваш вариант прост и шикарен.
А на php перенести можно, собственно как-то так:
<?php
$start=9266070005; $end=9266099923; $n=1;
//костыль для 32 бит
$start-=8000000000; $end-=8000000000;
$end++;
while($start<$end){
if(($end-$start)<$n){
$n/=10;
}elseif(($start/$n)%10==0 && $end-$start>=10*$n){
$n*=10;
}else{
//вывод маски, обрезаем последние разряды (десятки, сотни etc)
if($n!=1){
$result=substr(8000000000+$start,0,-(strlen($n)-1));
}else{
//а для единиц выводим полную маску
$result=8000000000+$start;
}
echo $result."\r\n";
$start+=$n;
}
}
?>

Answer 2

[throughtheether]

Я бы на вашем месте использовал префиксные деревья. Суммаризацию (вам же необходимо минимальное количество префиксов, или, как вы их называете, "масок"), скорее всего, придется писать самостоятельно.