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.
Odpowiedzi:
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]))
lambda x:x[0]-x[1].
[2,3,4,5] == xrange(2,6), nie xrange(2,5). Warto zdefiniować nowy typ danych obejmujących zakres.
for key, group in groupby(enumerate(data), lambda i: i[0] - i[1]): group = list(map(itemgetter(1), group))
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)]
print([i if i[0] != i[1] else i[0] for i in group(x)])
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)]
[j - i for i, j in enumerate(lst)]jest sprytny :-)
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]]
>>> getranges([2, 12, 13])Wyjścia: [[12, 13]]. Czy to było zamierzone?
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)]