如何进行逆“范围”，即根据一组数字创建一个紧凑的范围？

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']

编辑：我正在寻找解决方案，但我也欢迎使用其他语言的工作示例。更多的是想出一种优雅、高效的算法。额外的问题是:是否有任何编程语言对此有内置的方法？

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)]。你找出其余的:)

Answer 3

我想你可能会喜欢我的通用clojure解决方案。

(def r [1 2 3 9 10])

(defn successive? [a b]
  (= a (dec b)))

(defn break-on [pred s]
  (reduce (fn [memo n]
            (if (empty? memo)
              [[n]]
              (if (pred (last (last memo)) n)
                (conj (vec (butlast memo))
                      (conj (last memo) n))
                (conj memo [n]))))
          []
          s))

(break-on successive? r)