如何做一個相反的「範圍」，即根據一組數字創建一個緊湊的範圍？

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

Answer 3

這是一種優雅，但也有點噁心，這取決於你的觀點。 :)

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

說明：它由一個密鑰，其中所述密鑰是Rememberer對象使用itertools.groupby到組排序的元件一起。只要連續的一組項目屬於同一個範圍塊，RangeFinder類就會保留一個Rememberer對象。一旦你完成了一個給定的模塊，它將取代Rememberer，這樣密鑰就不會相等，groupby將會創建一個新組。由於groupby遍歷已排序的列表，它將元素逐個傳遞到rangestr，它通過記住第一個和最後一個元素並忽略它們之間的所有內容來構造字符串。

是否有任何實際的理由使用此代替9000's answer？可能不會;它基本上是相同的算法。

Answer 4

自9000打我吧，我就張貼代碼的第二部分，即從先前計算的打印PCRE般的範圍output加上添加類型檢查：

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

Answer 5

我想你可能會喜歡我的廣義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) 

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

這已經成爲相當可怕的，我想:)