建立一个“完整”的无重叠的数字范围

Question

我需要建立一个完整的“数字范围”集给定一系列的数字。我从一个清单开始，比如：

ID   START  
*    0  
a    4  
b    70  
c    700  
d    701  
e    85  

• 其中“def”是默认范围，应“填充”空白
• “重叠”是起始数据中的值（70700701）

需要以下结果：

^{pr2}$

我想弄清楚的是，是否有某种算法或设计模式可以解决这个问题。我有一些想法，但我想我应该先由“专家”来做。我用的是Python。在

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

• 构建一个“范围”列表，其中包含填充到整个长度的起始值和结束值。所以默认值是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了。测试：

^{pr2}$

如果你真的想要范围，你可以用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'): '*'}