Как сделать обратный `диапазон`, то есть создать компактный диапазон на основе набора чисел?

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

Я подумал, что вам может понравиться мое обобщенное решение для уловки.

(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 4

Давайте попробуем генераторы!

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

Это стало довольно страшно, я думаю:)

Answer 5

Поскольку 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 6

Это немного элегантно, но и отвратительно, в зависимости от вашей точки зрения.:)

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, который создает строку путем запоминания первого и последнего элемента и игнорирования всего, что находится между ними.

Есть лиесть практическая причина использовать это вместо ответа 9000 ?Возможно нет;это в основном тот же алгоритм.