Identify groups of consecutive numbers in a list

Я хотел бы определить группы последовательных чисел в списке, чтобы:

myfunc([2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20])

ВОЗВРАТ:

[(2,5), (12,17), 20]

И мне было интересно, как лучше всего это сделать (особенно, если в Python что-то встроено).

Редактировать: Примечание: Изначально я забыл упомянуть, что отдельные числа должны возвращаться как отдельные числа, а не как диапазоны.

ПРАВКА 2: Для ответа на новое требование OP

ranges = []
for key, group in groupby(enumerate(data), lambda (index, item): index - item):
    group = map(itemgetter(1), group)
    if len(group) > 1:
        ranges.append(xrange(group[0], group[-1]))
    else:
        ranges.append(group[0])

Вывод:

[xrange(2, 5), xrange(12, 17), 20]

Вы можете заменить xrange на range или любой другой пользовательский класс.

В документах Python есть очень аккуратный рецепт для этого:

from operator import itemgetter
from itertools import groupby
data = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17]
for k, g in groupby(enumerate(data), lambda (i,x):i-x):
    print(map(itemgetter(1), g))

Вывод:

[2, 3, 4, 5]
[12, 13, 14, 15, 16, 17]

Если вы хотите получить точно такой же результат, вы можете сделать это:

ranges = []
for k, g in groupby(enumerate(data), lambda (i,x):i-x):
    group = map(itemgetter(1), g)
    ranges.append((group[0], group[-1]))

вывод:

[(2, 5), (12, 17)]

РЕДАКТИРОВАТЬ: Пример уже описан в документации, но, возможно, мне следует объяснить его подробнее:

Ключом к решению является разность диапазоном, чтобы все последовательные числа отображались в одной группе.

Если данные были: [2, 3, 4, 5, 12, 13, 14, 15, 16, 17] То groupby(enumerate(data), lambda (i,x):i-x) эквивалентно следующему:

groupby(
    [(0, 2), (1, 3), (2, 4), (3, 5), (4, 12),
    (5, 13), (6, 14), (7, 15), (8, 16), (9, 17)],
    lambda (i,x):i-x
)

Лямбда-функция вычитает индекс элемента из значения элемента. Таким образом, когда вы применяете лямбду к каждому элементу. Вы получите следующие ключи для groupby:

[-2, -2, -2, -2, -8, -8, -8, -8, -8, -8]

groupby группирует элементы по одинаковому значению ключа, поэтому первые 4 элемента будут сгруппированы вместе и так далее.

Я надеюсь, это сделает его более читабельным.

python 3 версия может быть полезна новичкам

сначала импортируйте необходимые библиотеки

from itertools import groupby
from operator import itemgetter

ranges =[]

for k,g in groupby(enumerate(data),lambda x:x[0]-x[1]):
    group = (map(itemgetter(1),g))
    group = list(map(int,group))
    ranges.append((group[0],group[-1]))

more_itertools.consecutive_groups был добавлен в версии 4.0.

ДЕМОНСТРАЦИЯ

import more_itertools as mit


iterable = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20]
[list(group) for group in mit.consecutive_groups(iterable)]
# [[2, 3, 4, 5], [12, 13, 14, 15, 16, 17], [20]]

Код

Применяя этот инструмент, мы создаем функцию генератора, которая находит диапазоны последовательных чисел.

def find_ranges(iterable):
    """Yield range of consecutive numbers."""
    for group in mit.consecutive_groups(iterable):
        group = list(group)
        if len(group) == 1:
            yield group[0]
        else:
            yield group[0], group[-1]


iterable = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20]
list(find_ranges(iterable))
# [(2, 5), (12, 17), 20]

Реализация с исходным кодом эмулирует классический рецепт (как продемонстрировала @Nadia Alramli).

Примечание: more_itertools это пакет стороннего производителя, который можно установить через pip install more_itertools.

"Наивное" решение, которое я нахожу, по крайней мере, несколько читабельным.

x = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 22, 25, 26, 28, 51, 52, 57]

def group(L):
    first = last = L[0]
    for n in L[1:]:
        if n - 1 == last: # Part of the group, bump the end
            last = n
        else: # Not part of the group, yield current group and start a new
            yield first, last
            first = last = n
    yield first, last # Yield the last group


>>>print list(group(x))
[(2, 5), (12, 17), (22, 22), (25, 26), (28, 28), (51, 52), (57, 57)]

Предполагая, что ваш список отсортирован:

>>> from itertools import groupby
>>> def ranges(lst):
    pos = (j - i for i, j in enumerate(lst))
    t = 0
    for i, els in groupby(pos):
        l = len(list(els))
        el = lst[t]
        t += l
        yield range(el, el+l)


>>> lst = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17]
>>> list(ranges(lst))
[range(2, 6), range(12, 18)]