Zidentyfikuj grupy liczb ciągłych na liście

Chciałbym zidentyfikować grupy liczb ciągłych na liście, aby:

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

Zwroty:

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

I zastanawiałem się, jaki jest najlepszy sposób, aby to zrobić (szczególnie, jeśli jest coś wbudowanego w Python).

Edycja: Uwaga: początkowo zapomniałem wspomnieć, że poszczególne liczby powinny być zwracane jako pojedyncze liczby, a nie zakresy.

more_itertools.consecutive_groups został dodany w wersji 4.0.

Próbny

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

Kod

Korzystając z tego narzędzia, tworzymy funkcję generatora, która wyszukuje zakresy kolejnych liczb.

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]

Źródło realizacja emuluje klasyczny przepis (co wykazano przez @Nadia Alramli).

Uwaga: more_itertoolspakiet innej firmy można zainstalować za pośrednictwem pip install more_itertools.

EDYCJA 2: Aby odpowiedzieć na nowe wymaganie 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])

Wynik:

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

Możesz zamienić xrange na range lub inną własną klasę.

Dokumentacja Pythona ma na to bardzo zgrabny przepis :

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)

Wynik:

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

Jeśli chcesz uzyskać dokładnie taki sam wynik, możesz to zrobić:

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

wynik:

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

EDYCJA: Przykład jest już wyjaśniony w dokumentacji, ale może powinienem to wyjaśnić bardziej:

Kluczem do rozwiązania jest różnicowanie za pomocą zakresu, tak aby wszystkie kolejne liczby pojawiały się w tej samej grupie.

Jeśli dane były: [2, 3, 4, 5, 12, 13, 14, 15, 16, 17] To groupby(enumerate(data), lambda (i,x):i-x)jest równoważne z:

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
)

Funkcja lambda odejmuje indeks elementu od wartości elementu. Więc kiedy zastosujesz lambdę do każdej pozycji. Otrzymasz następujące klucze do funkcji Groupby:

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

groupby grupuje elementy według równej wartości klucza, więc pierwsze 4 elementy zostaną zgrupowane razem i tak dalej.

Mam nadzieję, że dzięki temu będzie bardziej czytelny.

python 3 wersja może być pomocna dla początkujących

zaimportuj najpierw wymagane biblioteki

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

Rozwiązanie „naiwne”, które uważam przynajmniej za dość czytelne.

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

Zakładając, że lista jest posortowana:

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

Oto coś, co powinno działać bez konieczności importowania:

def myfunc(lst):
    ret = []
    a = b = lst[0]                           # a and b are range's 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's start again with a single
    ret.append(a if a==b else (a,b))         # corner case for last single/range
    return ret

Należy pamiętać, że kod używający groupbynie działa tak, jak podano w Pythonie 3, więc użyj tego.

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

To nie używa standardowej funkcji - po prostu iiteruje nad wejściem, ale powinno działać:

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)

Zauważ, że wymaga, aby dane wejściowe zawierały tylko liczby dodatnie w porządku rosnącym. Powinieneś sprawdzić poprawność danych wejściowych, ale ten kod został pominięty dla przejrzystości.

Oto odpowiedź, którą wymyśliłem. Piszę kod, aby inni ludzie mogli go zrozumieć, więc jestem dość szczegółowy z nazwami zmiennych i komentarzami.

Najpierw funkcja szybkiego pomocnika:

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] 

A potem rzeczywisty kod:

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's 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

Przykładowy bieg:

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

zwroty:

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

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)

Wynik:

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

Używanie groupbyi countod itertoolsdaje nam krótkie rozwiązanie. Chodzi o to, że w rosnącej kolejności różnica między indeksem a wartością pozostanie taka sama.

Aby śledzić indeks, możemy użyć itertools.count , który sprawia, że ​​kod jest czystszy, jak użycie 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

Niektóre przykładowe dane wyjściowe:

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

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

Korzystanie z numpy + listy ze zrozumieniem:
Za pomocą funkcji numpy diff można zidentyfikować kolejne wpisy wektorów wejściowych, których różnica nie jest równa jeden. Należy wziąć pod uwagę początek i koniec wektora wejściowego.

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

Wynik:

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

Uwaga: Pominięto żądanie, aby poszczególne liczby były traktowane inaczej (zwracane jako indywidualne, a nie zakresy). Można to osiągnąć poprzez dalsze przetwarzanie końcowe wyników. Zwykle komplikuje to sprawy bez żadnych korzyści.

Krótkie rozwiązanie, które działa bez dodatkowego importu. Akceptuje wszelkie iterowalne dane, sortuje nieposortowane dane wejściowe i usuwa zduplikowane elementy:

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

Przykład:

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

To jest to samo, co rozwiązanie @ dansalmo, które wydało mi się niesamowite, choć trochę trudne do odczytania i zastosowania (ponieważ nie jest podane jako funkcja).

Zauważ, że można go łatwo zmodyfikować, aby wypluwał „tradycyjne” otwarte zakresy [start, end), np. Zmieniając instrukcję return:

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

Skopiowałem tę odpowiedź z innego pytania, które zostało oznaczone jako duplikat tego, aby było łatwiejsze do znalezienia (po tym, jak właśnie teraz ponownie szukałem tego tematu, znajdując najpierw tylko pytanie tutaj i nie jestem zadowolony z odpowiedzi dany).

Wersje autorstwa Marka Byersa , Andrei Ambu , SilentGhost , Nadii Alramli i truppo są proste i szybkie. Wersja „truppo” zachęciła mnie do napisania wersji, która zachowuje to samo zwinne zachowanie podczas obsługi rozmiarów kroków innych niż 1 (i wyświetla jako pojedyncze elementy, które nie rozciągają się więcej niż 1 krok z danym rozmiarem kroku). Jest podany tutaj .

>>> list(ranges([1,2,3,4,3,2,1,3,5,7,11,1,2,3]))
[(1, 4, 1), (3, 1, -1), (3, 7, 2), 11, (1, 3, 1)]