Построение «полного» диапазона номеров без перекрытий - PullRequest
Новая
       12

Построение «полного» диапазона номеров без перекрытий

0 голосов
/ 19 февраля 2009

Мне нужно построить полный набор «диапазон номеров», учитывая серию чисел. Я начинаю со списка, такого как: 

ID   START  
*    0  
a    4  
b    70  
c    700  
d    701  
e    85
  • где "def" - диапазон по умолчанию и должен "заполнить" пробелы
  • "перекрытия" - это значения (70, 700, 701) в начальных данных

И нужен следующий результат: 

ID  START  END  
*     0 - 39  
a     4 - 49  
*     5 - 69  
c   700 - 7009  
d   701 - 7019  
b   702 - 709  
*    71 - 849  
e    85 - 859  
*    86 - 9

Я пытаюсь выяснить, есть ли какой-нибудь алгоритм или шаблон проектирования для решения этой проблемы. У меня есть некоторые идеи, но я подумал, что в первую очередь буду руководствоваться ими "экспертами". Я использую Python.

Любые идеи / направления будут с благодарностью. Некоторые первоначальные идеи, которые у меня есть:

  • Создание списка «диапазона» с начальными и конечными значениями, дополненными до полной длины. Поэтому по умолчанию будет от 0000 до 9999
  • Создание списка "расщеплений", который создается на лету
  • Перебрать список «range», сравнивая каждое значение со значениями в списке разбиений.
  • В случае обнаружения перекрытия удалите значение в списке разделений и добавьте новый диапазон (ы).

1 Ответ

0 голосов
/ 19 февраля 2009 
import operator

ranges = {
    '4'  : 'a',
    '70' : 'b',
    '700': 'c',
    '701': 'd',
    '85' : 'e',
    '87' : 'a',
}

def id_for_value(value):
    possible = '*'
    for idvalue, id in sorted(ranges.iteritems()):
        if value.startswith(idvalue):
            possible = id
        elif idvalue > value:
            break
    return possible

Этого достаточно, чтобы узнать идентификатор определенного значения. Тестирование: 

assert id_for_value('10') == '*'
assert id_for_value('499') == 'a'
assert id_for_value('703') == 'b'
assert id_for_value('7007') == 'c'
assert id_for_value('7017') == 'd'
assert id_for_value('76') == id_for_value('83') == '*'
assert id_for_value('857') == 'e'
assert id_for_value('8716') == 'a'

Если вы действительно хотите диапазон, вы можете использовать itertools.groupby для его вычисления: 

def firstlast(iterator):
    """ Returns the first and last value of an iterator"""
    first = last = iterator.next()
    for value in iterator:
        last = value
    return first, last

maxlen = max(len(x) for x in ranges) + 1
test_range = ('%0*d' % (maxlen, i) for i in xrange(10 ** maxlen))
result = dict((firstlast(gr), id) 
              for id, gr in itertools.groupby(test_range, key=id_for_value))

Дает: 

{('0000', '3999'): '*',
 ('4000', '4999'): 'a',
 ('5000', '6999'): '*',
 ('7000', '7009'): 'c',
 ('7010', '7019'): 'd',
 ('7020', '7099'): 'b',
 ('7100', '8499'): '*',
 ('8500', '8599'): 'e',
 ('8600', '8699'): '*',
 ('8700', '8799'): 'a',
 ('8800', '9999'): '*'}
...