如何进行反向范围操作，即基于一组数字创建一个紧凑的范围？

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 解决方案，但我也欢迎其他语言的工作示例。更重要的是找到一种优雅、高效的算法。附加问题：是否有任何编程语言具有内置的此功能方法？

- Mathias Bynens

---

我怀疑没有比迭代列表更好的方法，这在自己编写时很容易实现。 - trutheality

@trutheality 我也是，因此才问这个问题。我希望这里有一个我错过的_优雅_的解决方案。手指交叉！ - Mathias Bynens

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

- Sven Marnach

---

不错！一个（愚蠢的）“问题”是list调用，这意味着你最终会不必要地复制列表的所有元素，这在99%的情况下都无关紧要，但可以通过使用我的答案中的rangestr函数避免。 - Danica

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)]。其余部分由您决定 :)

- 9000

---

“50-50” 应该只是 “50”，但我认为我可以自己处理。谢谢！ - Mathias Bynens

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)

- gf3

Answer 4

这有点优雅，但也有点令人反感，这取决于你的观点。 :)

import itertools

def rangestr(iterable):
    end = start = iterable.next()
    for end in iterable:
        pass
    return "%s" % start if start == end else "%s-%s" % (start, end)

class Rememberer(object):
    last = None

class RangeFinder(object):
    def __init__(self):
        self.o = Rememberer()

    def __call__(self, x):
        if self.o.last is not None and x != self.o.last + 1:
            self.o = Rememberer()
        self.o.last = x
        return self.o

def magic(iterable):
    return [rangestr(vals) for k, vals in
            itertools.groupby(sorted(iterable), RangeFinder())]


>>> magic([5,7,9,8,6, 21,20, 3,2,1, 22,23, 50])
['1-3', '5-9', '20-23', '50']

解释：它使用itertools.groupby通过键（键是一个Rememberer对象）将排序后的元素分组。当连续的一堆项目属于同一范围块时，RangeFinder类保持一个Rememberer对象。一旦您离开给定的块，它就会替换Rememberer，以便键不相等并且groupby将创建新的组。当groupby在排序列表上行走时，它将逐个将元素传递到rangestr中，rangestr通过记住第一个和最后一个元素并忽略中间所有内容来构造字符串。

与9000的答案相比，使用这个有没有实际意义？可能没有；基本上是相同的算法。

- Danica

---

我也考虑过类似的东西，使用纯迭代来计算 catamorphism :) 但是我无法发明出一种不需要模式匹配且不冗长的 FP 式解决方案。唉，这在 Python 中是缺失的。 - 9000

rangestr() 中的 try/except 块可以被 for end in iterable: pass 替换。另外请注意，从 Python 2.6 开始，iterable.next() 应该写成 next(iterable)。 - Sven Marnach

好点，for循环更好——我已经改用那种了。而且我确实知道next()，但由于仍有很多2.5用户，所以没有使用它。 - Danica

Answer 5

由于9000比我更快，我将只发布代码的第二部分，该部分从先前计算的output中打印类似于pcre的范围，再加上添加的类型检查：

for i in output:
    if not isinstance(i, int) or i < 0:
        raise Exception("Only positive ints accepted in pcre_ranges")
result = [ str(x[0]) if x[0] == x[1] else '%s-%s' % (x[0], x[1]) for x in output ]
print result

输出：['1-3'，'5-9'，'20-23'，'50']

- Frg

---

谢谢！“50-50”应该只是“50”，有什么简单的解决方案吗？ - Mathias Bynens

Answer 6

让我们尝试使用生成器！

# ignore duplicate values
l = sorted( set( [5,7,9,8,6, 21,20, 3,2,1, 22,23, 50] ) )

# get the value differences 
d = (i2-i1 for i1,i2 in zip(l,l[1:]))

# get the gap indices
gaps = (i for i,e in enumerate(d) if e != 1)

# get the range boundaries
def get_ranges(gaps, l):
  last_idx = -1
  for i in gaps:
    yield (last_idx+1, i)
    last_idx = i
  yield (last_idx+1,len(l)-1)

# make a list of strings in the requested format (thanks Frg!)
ranges = [ "%s-%s" % (l[i1],l[i2]) if i1!=i2 else str(l[i1]) \
  for i1,i2 in get_ranges(gaps, l) ]

我觉得这已经变得相当可怕了 :)

（这段话与IT技术无关）

- moooeeeep