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

День добрый, уважаемые коллеги.
Есть задача разложить номерную емкость вида "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. На выходе нужно получить минимальное количество масок, охватывающее исходный диапазон (включая первый и последний номер).
Заранее благодарен.
  • Вопрос задан
  • 276 просмотров
Решения вопроса 1
Mrrl
@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, не знаю.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@throughtheether
human after all
Я бы на вашем месте использовал префиксные деревья. Суммаризацию (вам же необходимо минимальное количество префиксов, или, как вы их называете, "масок"), скорее всего, придется писать самостоятельно.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы