group list of ints by continuous sequence

Question

I have a list of integers...

[1,2,3,4,5,8,9,10,11,200,201,202]

I would like to group them into a list of lists where each sublist contains integers whose sequence has not been broken. Like this...

[[1,5],[8,11],[200,202]]

I have a rather clunky work around...

lSequenceOfNum = [1,2,3,4,5,8,9,10,11,200,201,202]

lGrouped = []
start = 0
for x in range(0,len(lSequenceOfNum)):
    if x != len(lSequenceOfNum)-1:
        if(lSequenceOfNum[x+1] - lSequenceOfNum[x]) > 1:
            lGrouped.append([lSequenceOfNum[start],lSequenceOfNum[x]])
            start = x+1

    else:
        lGrouped.append([lSequenceOfNum[start],lSequenceOfNum[x]])
print lGrouped

It is the best I could do. Is there a more "pythonic" way to do this? Thanks..

Think of it in terms of where the jumps are instead of where the ranges are. You can store the results in a simple array of ints where each entry is an index corresponding to a jump in the original array. I think this is simpler... and on the off-chance this is going to be reusable or library code you can encapsulate all of that in the workings of a class. — djechlin, May 02 '12 at 19:40
I'm pretty sure this is a duplicate although I can't look for it right now. — jamylak, May 02 '12 at 22:06

Jeff Mercado · Accepted Answer · 2012-05-02T19:58:40.917

13

Assuming the list will always be in ascending order:

from itertools import groupby, count

numberlist = [1,2,3,4,5,8,9,10,11,200,201,202]

def as_range(g):
    l = list(g)
    return l[0], l[-1]

print [as_range(g) for _, g in groupby(numberlist, key=lambda n, c=count(): n-next(c))]

edited May 02 '12 at 19:58

answered May 02 '12 at 19:51

Jeff Mercado

129,526
32
251
272

score 5 · Answer 2 · edited May 23 '17 at 12:17

I realised I had overcomplicated this a little, far easier to just count manually than use a slightly convoluted generator:

def ranges(seq):
    start, end = seq[0], seq[0]
    count = start
    for item in seq:
        if not count == item:
            yield start, end
            start, end = item, item
            count = item
        end = item
        count += 1
    yield start, end

print(list(ranges([1,2,3,4,5,8,9,10,11,200,201,202])))

Producing:

[(1, 5), (8, 11), (200, 202)]

This method is pretty fast:

This method (and the old one, they perform almost exactly the same):

python -m timeit -s "from test import ranges" "ranges([1,2,3,4,5,8,9,10,11,200,201,202])"
1000000 loops, best of 3: 0.47 usec per loop

Jeff Mercado's Method:

python -m timeit -s "from test import as_range; from itertools import groupby, count" "[as_range(g) for _, g in groupby([1,2,3,4,5,8,9,10,11,200,201,202], key=lambda n, c=count(): n-next(c))]"
100000 loops, best of 3: 11.1 usec per loop

That's over 20x faster - although, naturally, unless speed matters this isn't a real concern.

My old solution using generators:

import itertools

def resetable_counter(start):
    while True:
        for i in itertools.count(start):
            reset = yield i
            if reset:
                start = reset
                break

def ranges(seq):
    start, end = seq[0], seq[0]
    counter = resetable_counter(start)
    for count, item in zip(counter, seq): #In 2.x: itertools.izip(counter, seq)
        if not count == item:
            yield start, end
            start, end = item, item
            counter.send(item)
        end = item
    yield start, end

print(list(ranges([1,2,3,4,5,8,9,10,11,200,201,202])))

Producing:

[(1, 5), (8, 11), (200, 202)]

@Abhijit Quite sure, I tested it. Have you found it to fail? — Gareth Latty, May 02 '12 at 21:02
Well not sure, but the o/p is not what it should be expected. Can you please have a look into this [IDEONE RUN](http://ideone.com/3sCnZ) — Abhijit, May 02 '12 at 21:04
@Abhijit Just checked, this appears to be a Python 2.x vs 3.x issue. Under 3.x it works fine... I'll try and figure out why. — Gareth Latty, May 02 '12 at 21:06
Of course, `zip()` isn't lazy in 2.x - there you need [`itertools.izip()`](http://docs.python.org/library/itertools.html#itertools.izip) - Now [Fixed](http://ideone.com/R4jBK) — Gareth Latty, May 02 '12 at 21:10

Abhijit · Answer 3 · 2012-05-02T20:58:27.987

You can do this efficiently in three steps

given

list1=[1,2,3,4,5,8,9,10,11,200,201,202]

Calculate the discontinuity

     [1,2,3,4,5,8,9,10,11 ,200,201,202]
-      [1,2,3,4,5,8,9 ,10 ,11 ,200,201,202]
----------------------------------------
       [1,1,1,1,3,1,1 ,1  ,189,1  ,1]
(index) 1 2 3 4 5 6 7  8   9   10  11 
                *          *
rng = [i+1 for i,e in enumerate((x-y for x,y in zip(list1[1:],list1))) if e!=1] 
>>> rng
[5, 9]

Add the boundaries

rng = [0] + rng + [len(list1)]
>>> rng
[0, 5, 9,12]

now calculate the actual continuity ranges

[(list1[i],list1[j-1]) for i,j in zip(list2,list2[1:])]
[(1, 5), (8, 11), (200, 202)]

LB                [0,   5,    9,  12]
UB             [0, 5,   9,    12]
     -----------------------
indexes (LB,UB-1) (0,4) (5,8) (9,11)

score 1 · Answer 4 · answered Jun 28 '16 at 09:49

1

The question is quite old, but I thought I'll share my solution anyway

Assuming import numpy as np

a = [1,2,3,4,5,8,9,10,11,200,201,202]

np.split(a, array(np.add(np.where(diff(a)>1),1)).tolist()[0])

answered Jun 28 '16 at 09:49

Aguy

7,851
5
31
58

score 0 · Answer 5 · answered May 02 '12 at 19:43

pseudo code (with off-by-one errors to fix):

jumps = new array;
for idx from 0 to len(array)
if array[idx] != array[idx+1] then jumps.push(idx);

I think this is actually a case where it makes sense to work with the indices (as in C, before java/python/perl/etc. improved upon this) instead of the objects in the array.

Tobu · Answer 6 · 2012-05-02T20:02:06.323

Here's a version that should be easy to read:

def close_range(el, it):
    while True:
        el1 = next(it, None)
        if el1 != el + 1:
            return el, el1
        el = el1

def compress_ranges(seq):
    iterator = iter(seq)
    left = next(iterator, None)
    while left is not None:
        right, left1 = close_range(left, iterator)
        yield (left, right)
        left = left1

list(compress_ranges([1, 2, 3, 4, 5, 8, 9, 10, 11, 200, 201, 202]))

score 0 · Answer 7 · edited May 23 '17 at 12:32

Similar questions:
Python - find incremental numbered sequences with a list comprehension
Pythonic way to convert a list of integers into a string of comma-separated ranges

input = [1, 2, 3, 4, 8, 10, 11, 12, 17]

i, ii, result = iter(input), iter(input[1:]), [[input[0]]]
for x, y in zip(i,ii):
    if y-x != 1:
        result.append([y])
    else:
        result[-1].append(y)

>>> result
[[1, 2, 3, 4], [8], [10, 11, 12], [17]]

>>> print ", ".join("-".join(map(str,(g[0],g[-1])[:len(g)])) for g in result)
1-4, 8, 10-12, 17

>>> [(g[0],g[-1])[:len(g)] for g in result]
[(1, 4), (8,), (10, 12), (17,)]

group list of ints by continuous sequence

7 Answers7

Linked

Related