Python - find incremental numbered sequences with a list comprehension

Question

I have a sequence of numbers in a list and I'm looking for an elegant solution, preferably list comprehension, to get the individual sequences (including single values). I have solved this small problem but it is not very pythonic.

The following list defines an input sequence:

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

The desired output should be:

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

Could there be two identical numbers in a row, i.e, `[1,2,2,3,5]`? — TerryA, May 01 '13 at 09:02
No, all numbers are unique and n + 1 will always be greater than n. — skovsgaard, May 01 '13 at 09:14

score 13 · Accepted Answer · answered May 01 '13 at 08:46

13

>>> from itertools import groupby, count
>>> nums = [1, 2, 3, 4, 8, 10, 11, 12, 17]
>>> [list(g) for k, g in groupby(nums, key=lambda n, c=count(): n - next(c))]
[[1, 2, 3, 4], [8], [10, 11, 12], [17]]

answered May 01 '13 at 08:46

jamylak

128,818
30
231
230

1

Can you see into the future? That's just... amazing. – TerryA May 01 '13 at 08:46
@Haidro it's not mine though :P – jamylak May 01 '13 at 08:47
1

It works - but it's not really self-explaining code. – Howard May 01 '13 at 08:47
@jamylak Ah, where from? – TerryA May 01 '13 at 08:47
Does it work by making sure the difference between each element is 1? ( in n - next(c) ) – HennyH May 01 '13 at 08:49
@Haidro I can't find the exact post. It was a recipe from `itertools` I believe. – jamylak May 01 '13 at 08:51
3

@HennyH: No, `c` is a counter, so it gives each element in the list an index (`0`, `1`, etc.) then groups values on the difference between their index and their actual value. `[1, 2, 3, 4]` all differ from their index by `1`, `[8]` differs from it's index by 4, etc. – Martijn Pieters May 01 '13 at 08:53
@MartijnPieters Ahh, that's ingenious! – HennyH May 01 '13 at 08:55
I found the other similar question, it's a superset of this one, I posted it as a possible duplicate – jamylak May 01 '13 at 09:12
1

I found [this blog post](http://jonathanchang.org/coding/group-consecutive-number-ranges) showing off this technique. And an earlier reference to it on [CodeReview](http://codereview.stackexchange.com/questions/5196/grouping-consecutive-numbers-into-ranges-in-python-3-2). – Martijn Pieters May 01 '13 at 10:06
But Gnibblers reference here is still the earliest I can locate. – Martijn Pieters May 01 '13 at 10:15
@MartijnPieters Earlier one: http://stackoverflow.com/questions/2154249/identify-groups-of-continuous-numbers-in-a-list Maybe @gnibbler was first to make the `count` edit, which I like more. Also look at the quote in that post: "Python docs have a very neat recipe for this:" There's a link there that no longer works. Ahh they have removed *examples* since 2.6, here's the last one: http://docs.python.org/2.6/library/itertools.html#examples – jamylak May 01 '13 at 10:19
@jamylak: The 2.4 Tex documentation has it, see the [mercurial repository version](http://hg.python.org/cpython/file/2.4/Doc/lib/libitertools.tex#l425). Indeed, the 2.6 [rest source](http://hg.python.org/cpython/file/2.6/Doc/library/itertools.rst#l596) also lists it still. – Martijn Pieters May 01 '13 at 10:24
@jamylak: It was present in the docs from python 2.4 until 2.6; [Raymond's commit that removed them](http://hg.python.org/cpython/rev/4cddef144428) doesn't give much in the way of reasoning for their removal. – Martijn Pieters May 01 '13 at 10:30
@MartijnPieters Not sure why they were removed... actually [this](http://code.activestate.com/recipes/303279-getting-items-in-batches/#c7) might be the first use or close enough – jamylak May 01 '13 at 10:36
We should really move this to the [Python chat room](http://chat.stackoverflow.com/rooms/6/python). :-) I discounted that reference because it doesn't batch by consecutive numbers, but batches items instead (it is a variant of the grouper recipe). – Martijn Pieters May 01 '13 at 10:38
@MartijnPieters Thanks but I think I've taken this too far now! I should get back to work :) – jamylak May 01 '13 at 10:40
1

@jamylak: And the [original commit](http://hg.python.org/cpython/diff/897de9208199/Doc/lib/libitertools.tex) for the example credits Guido with the idea, and was made in 2004. – Martijn Pieters May 01 '13 at 10:40

score 8 · Answer 2 · answered May 01 '13 at 09:08

Pythonic means simple, straightforward code, and not one-liners.

def runs(seq):
    result = []
    for s in seq:
        if not result or s != result[-1][-1] + 1:
            # Start a new run if we can't continue the previous one.
            result.append([])
        result[-1].append(s)
    return result

print runs([1, 2, 3, 4, 8, 10, 11, 12, 17])

Python - find incremental numbered sequences with a list comprehension

2 Answers2

Linked