How to do an inverse `range`, i.e. create a compact range based on a set of numbers?

numbers, pcre, python, range

Solution

A nice trick to simplify the code is to look at the difference of each element of the sorted list and its index:

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

prints

[1, 1, 2, 2]

Each run of the same number corresponds to a run of consecutive numbers in `a`. We can now use `itertools.groupby()` to extract these runs. Here's the complete code:

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

printing

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

Problem

Python has a `range` method, which allows for stuff like: ``` >>> range(1, 6) [1, 2, 3, 4, 5] ``` What I’m looking for is kind of the opposite: take a list of numbers, and return the start and end. ``` >>> magic([1, 2, 3, 4, 5]) [1, 5] # note: 5, not 6; this differs from `range()` ``` This is easy enough to do for the above example, but is it possible to allow for gaps or multiple ranges as well, returning the range in a PCRE-like string format? Something like this: ``` >>> magic([1, 2, 4, 5]) ['1-2', '4-5'] >>> magic([1, 2, 3, 4, 5]) ['1-5'] ``` Edit: I’m looking for a Python solution, but I welcome working examples in other languages as well. It’s more about figuring out an elegant, efficient algorithm. Bonus question: is there any programming language that has a built-in method for this?

Original source