разбить диапазон

конечный автомат (ну или рег. выражения)

Может вам поможет вот этот код? Он создает генератор диапазонов

class crange(object):
    def __init__(self, k):
        self.k = k
    def __call__(self, x):
        if self.k <= 0:
            return None
        if self.k > x:
            self.k -= x
            return xrange(self.k, self.k+x)
        x = self.k
        self.k = 0
        return xrange(0, x)

сr = crange(1000000) # Задаем правую границу диапазона
cr(2000)  # просим диапазон [0, 2000]
cr(3000)  # просим диапазон [2001, 3000]

Если я правильно понял задачу, то подойдёт что-то такое, например:

ranges = ({'from': 1000000, 'to': 1999999, 'prefix': 1},
          {'from': 2000000, 'to': 2099999, 'prefix': 20},
          {'from': 2100000, 'to': 2189999, 'prefix': lambda x: int(x / 10000)})

def get_prefix(value):
    for d in ranges:
        if value >= d['from'] and value <= d['to']:
            if hasattr(d['prefix'], '__call__'):
                return d['prefix'](value)
            else:
                return d['prefix']

print(get_prefix(1234567)) # 1
print(get_prefix(2000001)) # 20
print(get_prefix(2182999)) # 218

И так далее. Но наверняка будут и решения покрасивее.

поиск префикса по разбитому диапазону уже реализован. трудности в том что бы найти эти разбитые диапазоны.
Т.Е найти поддиапазон 1 000 000 по 1 999 999 из большого диапазона 1 000 000 до 2 192 999.

думаю как то так надо двигаться . добить до целого миллиона
потом добить до целых ста тысяч и тд.
но если диапазон 2 193 000 по 3 000 000 то наоборот добить до целой тыщи, добить до целых 10 тысяч и тд.

хотя возможно можно как то по другому это сделать. собственно мой вопрос в этом - найти диапазоны .

поиск префикса по разбитому диапазону уже реализован. трудности в том что бы найти эти разбитые диапазоны.
Т.Е найти поддиапазон 1 000 000 по 1 999 999 из большого диапазона 1 000 000 до 2 192 999.

Меня смущает слово «найти». Откуда берутся эти числа для обозначения границ диапазонов «1 999 999, 2 099 999, 2 189 999, 2 192 999, 2 199 999, 2 999 999». Они формируются по какому-то правилу или просто изначально заданы и всегда неизменны? И что далее должно произойти с найденным поддиапазоном?

Откуда берутся эти числа для обозначения границ диапазонов «1 999 999, 2 099 999, 2 189 999, 2 192 999, 2 199 999, 2 999 999»

они берутся исходя из такой логики
1 000 000 по 1 999 999 префикс для диапазона 1
то есть любая строка из этого диапазона начинающаяся на 1 ( будет входить в диапазон этих номеров)

2 000 000 по 2 099 999 префикс для диапазона 20
то есть любая строка начинающаяся на 20 . тут мы не можем использовать префикс просто 2 поскольку изначальный диапазон
от 1 000 000 до 2 192 999 в который не входят все цифры начинающиеся на 2.

и тд.

вообще это получается задача обратная задаче поиска направления по префиксу.

например в SQL бд прописаны префиксы 1, 20 , 210 итд. мы к нему делаем запрос select like . и sql отдает нам наиболее подходящий префикс по этому номеру. префиксы могут быть разной длинны. но sql находит его по наибольшему совпадению от начала номера.

А зачем вообще понадобилось разбивать диапазоны на поддиапазоны? У тебя есть код который заданному номеру сопоставляет префикс, разве этого не достаточно?

например в SQL бд прописаны префиксы 1, 20 , 210 итд. мы к нему делаем запрос select like . и sql отдает нам наиболее подходящий префикс по этому номеру. префиксы могут быть разной длинны. но sql находит его по наибольшему совпадению от начала номера.

Ok. Вот эта часть реализована в SQL, и уже работает, и менять её не надо. Я правильно понимаю? Теперь представим всё, что у тебя происходит, в виде блок-схемы.

данные на входе --> Чёрный ящик --> данные на выходе.

они берутся исходя из такой логики 1 000 000 по 1 999 999 префикс для диапазона 1 то есть любая строка из этого диапазона начинающаяся на 1 ( будет входить в диапазон этих номеров)

2 000 000 по 2 099 999 префикс для диапазона 20 то есть любая строка начинающаяся на 20 . тут мы не можем использовать префикс просто 2 поскольку изначальный диапазон от 1 000 000 до 2 192 999 в который не входят все цифры начинающиеся на 2.

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

Теперь вопрос. Что из себя представляют данные на входе: это числа или строки; сколько их: единицы, сотни, миллионы, миллиарды?

Потом что-то происходит с этими данными в чёрном ящике.

Второй вопрос. Что появляется на выходе чёрного ящика: числа или строки; сколько их?

А зачем вообще понадобилось разбивать диапазоны на поддиапазоны?

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

У тебя есть код который заданному номеру сопоставляет префикс, разве этого не достаточно?

этот код работает когда в список префиксов уже сформирован. задача найти эти префиксы.

то что я указал в условиях что префикс для 1)-1 000 000 по 1 999 999 равен 1 - это я всего лишь указал разложив в уме диапазон. задача найти этот префикс.

Честно говоря, я до сих пор ничего не понимаю.

Префиксы даны или их надо сформировать? Если сформировать то по какому принципу?

Почему есть префикс 20, 21 итп, но нет 10, 11?

Короче, всё это очень странно.

Ok. Вот эта часть реализована в SQL, и уже работает, и менять её не надо. Я правильно понимаю? Теперь представим всё, что у тебя происходит, в виде блок-схемы.

Задача сформировать эти префиксы - допустим для бд sql что бы по ним определять куда направлять этот номер. задача обратная - для бд найти эти префиксы, и так что бы их число было как можно меньше.
вы поняли немножко не верно. для того что бы схема с черным ящиком заработала и нужно найти эти префиксы.

можно еще вот так провести аналогию.
найти адрес сети по известному диапазону ip адресов и маске ( но только для десятичных чисел)
эту задачу решает маршрутизатор когда к нему прилетает пакет из маски вычисляет адрес и рулит в разные gateway
но для десятичных логика ИЛИ не подойдет. это очень грубая аналогия.

Префиксы даны или их надо сформировать? Если сформировать то по какому принципу?

изначально префиксов нет. их нужно сформировать.
по принципу: от 1 000 000 до 2 192 999
x- любое число
1)в этот диапазон входит любой номер начинающийся на 1 XXX XXX
2)так же в этот диапазон пролезет любое число начинающееся на
2 0ХХ ХХХ
3)так же в этот диапазон пролезет войдет любое число начинающееся на 2 10х ххх или 211х ххх, .. 218x xxx
4) 2190xxx 2191xxx 2192xxх

собственно надо найти эти числа return [1, 20, 210, 211,218 и тд]

Почему есть префикс 20, 21 итп, но нет 10, 11?

префикс 10 может быть, но он не нужен поскольку - он и так уже удовлетворяет условию начинающийся на 1 . 11 - тоже начинается на 1 .

префикс 10 может быть, но он не нужен поскольку - он и так уже удовлетворяет условию начинающийся на 1

Тогда по логике префикс 20, 210 итп не нужны, они уже включены в префикс 2.

В общем, я не понимаю логики. Если не секрет, какая глобальная задача решается?

ex.py:

res = []
j = 2192999
while(j > 0):
    res.append(j)
    j = (j / 10) - 1 if (j % 10 == 0) else (j - 1)
print sorted(res)

aedeph@aedeph:~/sandbox/python$ python ex.py
[1, 20, 210, 211, 212, 213, 214, 215, 216, 217, 218, 2190, 2191, 21920, 21921, 21922, 21923, 21924, 21925, 21926, 21927, 21928, 219290, 219291, 219292, 219293, 219294, 219295, 219296, 219297, 219298, 2192990, 2192991, 2192992, 2192993, 2192994, 2192995, 2192996, 2192997, 2192998, 2192999]

Но вообще, тебе это не нужно. Тебе нужно немедленно в букварь для грамотности и в учебник по дискретной математике для нормального формулирование мыслей.

s/ание/ания/

ps:

в функциональном стиле:

def fun(x):
    if (x > 0):
        return fun((x / 10) - 1 if (x % 10 == 0) else (x - 1)) + [x]
    else:
        return []
print fun(2192999)

в функциональном стиле не для девочек:

print (lambda f: (lambda x: x(x))(lambda y: f(lambda z: y(y)(z))))(lambda f: lambda x: (f(x / 10 - 1 if (x % 10 == 0) else x-1) if x > 1 else []) + [x])(2192999) 

j/10

Вы, батенька, так пишете, как будто оператор деления «/» работает одинаково во всех версиях пайтона. Вы, кстати, на какой запускали?

2.7.3, разумеется. УМВР.

Но я согласен, s/\//\/\// было бы лучше.

спасибо за предложенное решение.

думаю над тем как бы сделать так что бы сократить результат.
ведь по идее для 1000000 до 2192999
результат должен быть
[1, 20, 210, 211, 212, 213, 214, 215, 216, 217, 218, 2190, 2191, 2192]
нет необходимости расписывать префикс 2192 - потому что все номера начинающиеся с этого префикса 2192 входят в диапазон.
И как быть если диапазон задан с нижней границей 2193000 по 3001299 ?
согласен что условия изложил сумбурно, я больше связист чем программист. Не сочтите за труд просветите, как будет звучать условие в терминах дискретной математики ?

Тогда по логике префикс 20, 210 итп не нужны, они уже включены в префикс 2.

префиксы 20, 210 нужны ибо диапазон 1000000 до 2192999
то есть может быть число 2666111 которое не входит в этот диапазон. а использовав префикс 20 мы явно указываем, что в него подпадают все числа начинающиеся на 20ххххх.

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

как бы сделать так что бы сократить результат

res = []
j = 2192999
while(j > 0):
    if (j % 10 == 9)
         j = j / 10
    else
         res.append(j)
         j = (j / 10) - 1 if (j % 10 == 0) else (j - 1)
print list(reversed(res))

И как быть если диапазон задан с нижней границей 2193000 по 3001299 ?

Бить на две области относительно 3000000, с нижней частью разбираться домножив на -1.

Не сочтите за труд просветите

Сочту.

Понял, надо найти набор префиксов для заданного диапазона. Товарищ сверху, вроде, написал код. Речь идёт об IP-адресах? Попробуй так же посмотреть в гугле что-то типа «IP split address range into subnets».

Готовый код для IP-адресов: http://pythonhosted.org/netaddr/tutorial_01.html#support-for-non-standard-add...

Спасибо Огроменское. уже пол дня вникаю, ( не могу столько переменных в голове держать) где бы куда бы пойти учится, что бы такие задачки щелкать на раз...
Еще интересно сколько времени заняла реализация...

Еще интересно сколько времени заняла реализация...

на алгоритм - минут 30, лежа в ванне

на реализацию - минут 60

на обфускациюабстракции - часа 3

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

ну ок, вот вариант без абстракций, лол

def min_order(num):
    return 1 if num%10 else 10*min_order(num//10)

def prefixes(low, high):
    
    def forward(num, order):
        nxt = num + order
        if nxt == high + 1:
            return [num//order]
            
        if nxt > high + 1:
            return backward(num, order//10)
                        
        if not num%(order*10):
            return forward(num, order*10)
            
        return [num//order] + forward(nxt, order)

    def backward(num, order):
        nxt = num + order
        if nxt == high + 1:
             return [num//order]
             
        if nxt > high + 1:
            return backward(num, order//10)
                        
        return [num//order] + backward(nxt, order)
        
    return forward(low, min_order(low))

Валидностью я особо не заморачивался, так что вполне возможно оно на каких-то входных данных свалится.

Оплачивать не надо)