Определить группы непрерывных чисел в списке

Ответ 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.

Ответ 2

РЕДАКТИРОВАТЬ 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):ix) эквивалентно следующему:

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
)

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

[-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]))

Ответ 3

"Наивное" решение, которое я считаю немного читаемым, по крайней мере.

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)]

Ответ 4

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

>>> 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)]

Ответ 5

Здесь он должен работать, без необходимости импорта:

def myfunc(lst):
    ret = []
    a = b = lst[0]                           # a and b are range bounds

    for el in lst[1:]:
        if el == b+1: 
            b = el                           # range grows
        else:                                # range ended
            ret.append(a if a==b else (a,b)) # is a single or a range?
            a = b = el                       # let start again with a single
    ret.append(a if a==b else (a,b))         # corner case for last single/range
    return ret

Ответ 6

Обратите внимание, что код с использованием groupby не работает, как указано в Python 3, поэтому используйте это.

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

Ответ 7

Это не использует стандартную функцию - она ​​просто просматривает ввод, но он должен работать:

def myfunc(l):
    r = []
    p = q = None
    for x in l + [-1]:
        if x - 1 == q:
            q += 1
        else:
            if p:
               if q > p:
                   r.append('%s-%s' % (p, q))
               else:
                   r.append(str(p))
            p = q = x
    return '(%s)' % ', '.join(r)

Обратите внимание, что для ввода требуется только положительные числа в порядке возрастания. Вы должны подтвердить ввод, но этот код для ясности опущен.

Ответ 8

Вот ответ, который я придумал. Я пишу код для других людей, чтобы понять, поэтому я довольно многословный с именами переменных и комментариями.

Сначала быстрая вспомогательная функция:

def getpreviousitem(mylist,myitem):
    '''Given a list and an item, return previous item in list'''
    for position, item in enumerate(mylist):
        if item == myitem:
            # First item has no previous item
            if position == 0:
                return None
            # Return previous item    
            return mylist[position-1] 

И тогда фактический код:

def getranges(cpulist):
    '''Given a sorted list of numbers, return a list of ranges'''
    rangelist = []
    inrange = False
    for item in cpulist:
        previousitem = getpreviousitem(cpulist,item)
        if previousitem == item - 1:
            # We're in a range
            if inrange == True:
                # It an existing range - change the end to the current item
                newrange[1] = item
            else:    
                # We've found a new range.
                newrange = [item-1,item]
            # Update to show we are now in a range    
            inrange = True    
        else:   
            # We were in a range but now it just ended
            if inrange == True:
                # Save the old range
                rangelist.append(newrange)
            # Update to show we're no longer in a range    
            inrange = False 
    # Add the final range found to our list
    if inrange == True:
        rangelist.append(newrange)
    return rangelist

Пример выполнения:

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

возвращает:

[[2, 5], [12, 17]]

Ответ 9

import numpy as np

myarray = [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20]
sequences = np.split(myarray, np.array(np.where(np.diff(myarray) > 1)[0]) + 1)
l = []
for s in sequences:
    if len(s) > 1:
        l.append((np.min(s), np.max(s)))
    else:
        l.append(s[0])
print(l)

Вывод:

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

Ответ 10

Использование списков numpy +:
С помощью функции numpy diff могут быть определены последовательные входные векторные записи, что их разность не равна единице. Начало и конец входного вектора необходимо учитывать.

import numpy as np
data = np.array([2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20])

d = [i for i, df in enumerate(np.diff(data)) if df!= 1] 
d = np.hstack([-1, d, len(data)-1])  # add first and last elements 
d = np.vstack([d[:-1]+1, d[1:]]).T

print(data[d])

Выход:

 [[ 2  5]   
  [12 17]   
  [20 20]]

Примечание. Запрос о том, что отдельные числа должны обрабатываться по-разному (возвращаются как отдельные, а не диапазоны), был опущен. Это может быть достигнуто путем дальнейшей обработки результатов. Обычно это усложняет ситуацию, не принося никакой пользы.

Ответ 11

Краткое решение, которое работает без дополнительного импорта. Он принимает любые повторяемые, сортирует несортированные входные данные и удаляет дублирующиеся элементы:

def ranges(nums):
    nums = sorted(set(nums))
    gaps = [[s, e] for s, e in zip(nums, nums[1:]) if s+1 < e]
    edges = iter(nums[:1] + sum(gaps, []) + nums[-1:])
    return list(zip(edges, edges))

Пример:

>>> ranges([2, 3, 4, 7, 8, 9, 15])
[(2, 4), (7, 9), (15, 15)]

>>> ranges([-1, 0, 1, 2, 3, 12, 13, 15, 100])
[(-1, 3), (12, 13), (15, 15), (100, 100)]

>>> ranges(range(100))
[(0, 99)]

>>> ranges([0])
[(0, 0)]

>>> ranges([])
[]

Это то же самое, что и решение @dansalmo, которое мне показалось поразительным, хотя и немного сложным для чтения и применения (поскольку оно не дано как функция).

Обратите внимание, что его можно легко изменить, чтобы он выплевывал "традиционные" открытые диапазоны [start, end), например, путем изменения оператора return:

    return [(s, e+1) for s, e in zip(edges, edges)]

Я скопировал этот ответ из другого вопроса, который был помечен как дубликат этого, чтобы облегчить его поиск (после того, как я только что снова искал эту тему, сначала нашел только вопрос здесь и не был удовлетворен ответами) дано).

Ответ 12

Использование groupby и count от itertools дает нам краткое решение. Идея состоит в том, что в возрастающей последовательности разница между индексом и значением останется неизменной.

Чтобы отслеживать индекс, мы можем использовать itertools.count, который делает код более чистым, используя enumerate:

from itertools import groupby, count

def intervals(data):
    out = []
    counter = count()

    for key, group in groupby(data, key = lambda x: x-next(counter)):
        block = list(group)
        out.append([block[0], block[-1]])
    return out

Некоторые примеры выходных данных:

print(intervals([0, 1, 3, 4, 6]))
# [[0, 1], [3, 4], [6, 6]]

print(intervals([2, 3, 4, 5]))
# [[2, 5]]