如何做一个反"范围",即根据一组数字创建一个紧凑的范围？

Question

Python有一个range方法,它允许以下内容:

>>> range(1, 6)
[1, 2, 3, 4, 5]

我正在寻找的是相反的:拿一个数字列表,并返回开始和结束.

>>> magic([1, 2, 3, 4, 5])
[1, 5] # note: 5, not 6; this differs from `range()`

这对于上面的示例来说很容易做到,但是是否可以允许间隙或多个范围,以类似PCRE的字符串格式返回范围？像这样的东西:

>>> magic([1, 2, 4, 5])
['1-2', '4-5']
>>> magic([1, 2, 3, 4, 5])
['1-5']

编辑:我正在寻找一个Python解决方案,但我也欢迎其他语言的工作示例.它更多的是要找出一个优雅,高效的算法.奖金问题:是否有任何编程语言具有内置方法？

Answer 1

简化代码的一个很好的技巧是查看排序列表的每个元素及其索引的区别:

a = [4, 2, 1, 5]
a.sort()
print [x - i for i, x in enumerate(a)]

版画

[1, 1, 2, 2]

每个相同数字的运行对应于一系列连续数字a.我们现在可以itertools.groupby()用来提取这些运行.这是完整的代码:

from itertools import groupby

def sub(x):
    return x[1] - x[0]

a = [5, 3, 7, 4, 1, 2, 9, 10]
ranges = []
for k, iterable in groupby(enumerate(sorted(a)), sub):
     rng = list(iterable)
     if len(rng) == 1:
         s = str(rng[0][1])
     else:
         s = "%s-%s" % (rng[0][1], rng[-1][1])
     ranges.append(s)
print ranges

印花

['1-5', '7', '9-10']

Answer 2

排序数字,找到连续范围(还记得RLE压缩吗？).

像这样的东西:

input = [5,7,9,8,6, 21,20, 3,2,1, 22,23, 50]

output = []
first = last = None # first and last number of current consecutive range
for item in sorted(input):
  if first is None:
    first = last = item # bootstrap
  elif item == last + 1: # consecutive
    last = item # extend the range
  else: # not consecutive
    output.append((first, last)) # pack up the range
    first = last = item
# the last range ended by iteration end
output.append((first, last))

print output

结果:[(1, 3), (5, 9), (20, 23), (50, 50)].你弄清楚其余的:)