Detect ranges in Python

Question

I'm trying to solve this exercise in my coursework:

Create a function named detect_ranges that gets a list of integers as a parameter. The function should then sort this list, and transform the list into another list where pairs are used for all the detected intervals. So 3,4,5,6 is replaced by the pair (3,7). Numbers that are not part of any interval result just single numbers. The resulting list consists of these numbers and pairs, separated by commas. An example of how this function works:

print(detect_ranges([2,5,4,8,12,6,7,10,13]))
[2,(4,9),10,(12,14)]

I couldn't comprehend the exercise topic and can't think of how I can detect range. Do you guys have any hints or tips?

For asking about homework questions, please read [this guideline](https://meta.stackoverflow.com/a/334823) for the section "Asking about homework". In any case, you were asked to sort the list, which your instructor may reference the [documentation on how to sort](https://docs.python.org/3/howto/sorting.html). As for detecting a range, it's a matter of iterating through the sorted list and find sequential elements to produce the output. Searching around you may find [a similar answer like this](https://stackoverflow.com/questions/2361945/detecting-consecutive-integers-in-a-list) — metatoaster, May 27 '21 at 03:57
This function would be better named `detect_ranges_after_sort`. (Or just extract the sorting step out of the function.) — Mateen Ulhaq, May 27 '21 at 04:05

Ank · Accepted Answer · 2021-05-27T09:34:41.133

Another way of doing this. Although this method will not be as efficient as the other one, but since its an exercise, it will be easier to follow.

I have used zip function in python to do some stuff I explained below, you can check it here to know more about it.

1. First sort the list data, so you get: [2, 4, 5, 6, 7, 8, 10, 12, 13]

2. Then find the differences of increasing values in list. Like (4-2),(5-4), .. If the difference is <=1, then it will be part of a range:

(Also, insert a 0 in the front, just to account for the 1st element and make the obtained list's length equal to original list)

>>> diff = [j-i for i, j in zip(lst[:-1], lst[1:])]
>>> diff.insert(0, 0)
>>> diff
[0, 2, 1, 1, 1, 1, 2, 2, 1]

3. Now get positions in above list where difference is >= 2. This is to detect the ranges:

(Again, insert a 0 in the front, just to account for the 1st element, and make sure it gets picked in range detection)

>>> ind = [i for i,v in enumerate(diff) if v >= 2]
>>> ind.insert(0, 0)
>>> ind
[0, 1, 6, 7]

So the ranges are 0 to 1, 1 to 6, and 6 to 7 in your original list.

4. Group the elements together that will form ranges, using the ind list obtained:

>>> groups = [lst[i:j] for i,j in zip(ind, ind[1:]+[None])]
>>> groups
[[2], [4, 5, 6, 7, 8], [10], [12, 13]]

5. Finally obtain your desired ranges:

>>> ranges = [(i[0],i[-1]+1) if len(i)>1 else i[0] for i in groups]
>>> ranges
[2, (4, 9), 10, (12, 14)]

Putting it all in a function detect_ranges:

def detect_ranges(lst):
    lst = sorted(lst)
    diff = [j-i for i, j in zip(lst[:-1], lst[1:])]
    diff.insert(0, 0)
    
    ind = [i for i,v in enumerate(diff) if v >= 2]
    ind.insert(0, 0)
    
    groups = [lst[i:j] for i,j in zip(ind, ind[1:]+[None])]
    ranges = [(i[0],i[-1]+1) if len(i)>1 else i[0] for i in groups]
    return ranges

Examples:

>>> lst = [2,6,1,9,3,7,12,45,46,13,90,14,92]
>>> detect_ranges(lst)
[(1, 4), (6, 8), 9, (12, 15), (45, 47), 90, 92]

>>> lst = [12,43,43,11,4,3,6,6,9,9,10,78,32,23,22,98]
>>> detect_ranges(lst)
[(3, 5), (6, 7), (9, 13), (22, 24), 32, (43, 44), 78, 98]

Mateen Ulhaq · Answer 2 · 2021-05-27T04:21:57.923

Iterate through the elements and save the start of each interval.

def detect_ranges(xs):
    it = iter(xs)
    try:
        start = next(it)
    except StopIteration:
        return
    prev = start

    for x in it:
        if prev + 1 != x:
            yield start, prev + 1
            start = x
        prev = x

    yield start, prev + 1

Usage:

>>> xs = [2, 4, 5, 6, 7, 8, 10, 12, 13]
>>> ranges = list(detect_ranges(xs))
>>> ranges
[(2, 3), (4, 9), (10, 11), (12, 14)]

If you want to reduce single item intervals like (2, 3) to 2, you can do:

>>> ranges = [a if a + 1 == b else (a, b) for a, b in ranges]
>>> ranges
[2, (4, 9), 10, (12, 14)]

Detect ranges in Python

2 Answers2