建立一个“完整的”数字范围w/out重叠

Question

我需要建立一个完整的“数字范围”给定的一系列数字。我开始与列表，诸如：

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。

任何想法/方向将不胜感激。我有一些初步想法：

• 建立一个“范围”列表w /开始&结束值填充到全长。因此，默认值为0000至9999
• 构建一个即时构建的“拆分”列表
• 循环“范围”列表将每个值与拆分列表中的值进行比较。
• 如果发现重叠，请删除拆分列表中的值并添加新的范围。

Answer 1

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 

这一点就足以知道某个值的ID。测试：

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'): '*'}