Разбивка номерных емкостей мобильной нумерации на диапазоны

Question

Есть две границы номерной ёмкости, например:

ОТ: 7902125000 - ДО : 7902129999

И необходимо вытащить диапазоны в формате: 7902125* 7902126* 7902127* 7902128* 7902129*

(и отдельные номера, если по ним нельзя выстроить диапазон номеров)

Есть сложности в том, что границы могут быть примерно такими:

ОТ: 7902125009 - ДО : 7902125023 из которого можно выделить только один диапазон 790212501* и отдельные номера: 7902125009, 7902125020 , 7902125021 , 7902125022, 7902125023

Как это можно на питоне реализовать?

Answer 1

Придумал такой алгоритм:

Ищем числа с нулями в конце и записываем их в таком формате: (число, кол-во нулей на конце)
Сортируем по убыванию количества нулей и по возрастанию самого числа. (-x[1], x[0])
Для каждой пары проверяем входит ли диапазон range(число, число+10**кол-во нулей) в исходный диапазон.
Если входит - вычитаем из общего диапазона и добавляем в список масок str(num)[:-zeros]+'*'.
После проверки всех пар (число, кол-во нулей на конце) остаются числа, для которых маска не "придумалась".

Получился такой код:

start = 7902125009
end = 7902125023

masks = []

def end_zeros(num: int) -> int:
    return len(str(num)) - len(str(num).rstrip('0'))

all_range = set(range(start, end+1))

num_zeros = []
for n in all_range: # pairs (num, tail_zeros)
    z = end_zeros(n)
    if z:
        num_zeros.append((n, z))
    
num_zeros.sort(key=lambda x: (-x[1], x[0])) # tail_zeros ASC, num DESC

for num, zeros in num_zeros:
    tmp_range = set(range(num, num+10**zeros))
    if tmp_range.issubset(all_range): # if range(num, num+10**zeros) in all_range
        all_range -= tmp_range # substract from all_range
        masks.append(str(num)[:-zeros]+'*') # adding mask to list of masks

for n in all_range: # no mathcing masks
    masks.append(str(n))

print(masks)

UPD:

start = 73519000000
end   = 73519099999

masks = []

def end_zeros(num: int) -> int:
    return len(str(num)) - len(str(num).rstrip('0'))

all_range = set(range(start, end+1))

num_zeros = []
for n in all_range: # pairs (num, tail_zeros)
    z = end_zeros(n)
    if z:
        num_zeros.append((n, z))
    
num_zeros.sort(key=lambda x: (-x[1], x[0])) # tail_zeros ASC, num DESC

for num, _zeros in num_zeros:
    for zeros in reversed(range(1, _zeros+1)): # decr tail zeros
        tmp_range = set(range(num, num+10**zeros))
        if tmp_range.issubset(all_range): # if range(num, num+10**zeros) in all_range
            all_range -= tmp_range # substract from all_range
            masks.append(str(num)[:-zeros]+'*') # adding mask to list of masks
    
for n in all_range: # no mathcing masks
    masks.append(str(n))

print(masks)

Answer 2

def ranges( first:str, last:str ):
    assert( len(first) == len(last) )
    assert( int(first) <= int(last) )

    if first == last:
        return [first]
    if first == "0" * len(first) and last== "9"* len(last):
        return ["*"]
    if first[0] == last[0]:
        return [ first[0]+v  for v in ranges( first[1:], last[1:] ) ]

    assert( int(first[0]) < int(last[0]) )
    return ranges( first, first[0] + "9"*(len(first)-1) ) \
        + ranges( str(int(first[0])+1) + "0"*(len(first)-1), last  )

если начало диапазона совпадает с концом - то решение единственное (без маски).
если начало диапазона состоит из одних нулей, а конец из девяток - то решение "*"
если первая цифра начала, совпадает с первой цифрой конца, то отбросим первую цифру, и решим задачу для урезанный диапазонов. (Потом припишем первую цифру к результату.)
если первая цифра начала, меньше чем первая цифра конца - разделим задачу на две, введя промежуточную точку: первая цифра диапазона + нужное количество девяток. (Следующее число за промежуточной точкой + первая цифра +1, и нули.)

test:

assert ranges( "7351900000" , "7902125023" ) == ['73519*', '7352*', '7353*', '7354*', '7355*', '7356*', '7357*', '7358*', '7359*', '736*', '737*', '738*', '739*', '74*', '75*', '76*', '77*', '78*', '7900*', '7901*', '79020*', '790210*', '790211*', '7902120*', '7902121*', '7902122*', '7902123*', '7902124*', '790212500*', '790212501*', '7902125020', '7902125021', '7902125022', '7902125023']
assert ranges( "7902125000" , "7902129999" ) == ['7902125*', '7902126*', '7902127*', '7902128*', '7902129*']

БЛОГ НА HUSL

Разбивка номерных емкостей мобильной нумерации на диапазоны

Ответы (2 шт):