Identificar grupos de números continuos en una lista.

Me gustaría identificar grupos de números continuos en una lista, de modo que:

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

Devoluciones:

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

Y me preguntaba cuál sería la mejor manera de hacer esto (especialmente si hay algo incorporado en Python).

Edición: Nota: originalmente olvidé mencionar que los números individuales deben devolverse como números individuales, no como rangos.

Se agregó more_itertools.consecutive_groups en la versión 4.0.

Manifestación

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

Código

Aplicando esta herramienta, hacemos una función de generador que encuentra rangos de números consecutivos.

 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] 

La implementación de origen emula una receta clásica (como lo demuestra @Nadia Alramli).

Nota: more_itertools es un paquete de terceros que se puede instalar a través de pip install more_itertools .

EDIT 2: Para responder al nuevo requisito 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]) 

Salida:

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

Puede reemplazar xrange con rango o cualquier otra clase personalizada.


Los documentos de Python tienen una receta muy buena para esto:

 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):ix): print map(itemgetter(1), g) 

Salida:

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

Si desea obtener el mismo resultado exacto, puede hacer esto:

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

salida:

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

EDITAR: El ejemplo ya está explicado en la documentación, pero tal vez debería explicarlo más:

La clave de la solución es diferenciar con un rango para que todos los números consecutivos aparezcan en el mismo grupo.

Si los datos fueron: [2, 3, 4, 5, 12, 13, 14, 15, 16, 17] Entonces groupby(enumerate(data), lambda (i,x):ix) es equivalente a lo siguiente:

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

La función lambda resta el índice del elemento del valor del elemento. Así que cuando se aplica la lambda en cada elemento. Obtendrás las siguientes claves para groupby:

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

Agrupe los elementos por igual valor clave, de modo que los primeros 4 elementos se agruparán y así sucesivamente.

Espero que esto lo haga más legible.

python 3 versión de python 3 puede ser útil para los principiantes

Importar las bibliotecas requeridas primero

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

La solución “ingenua” que encuentro al menos algo legible.

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

Suponiendo que su lista está ordenada:

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

Aquí es algo que debería funcionar, sin necesidad de ninguna importación:

 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 

Tenga en cuenta que el código que usa groupby no funciona como se indica en Python 3, así que use esto.

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

Esto no usa una función estándar, solo se analiza en la entrada, pero debería funcionar:

 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) 

Tenga en cuenta que requiere que la entrada solo contenga números positivos en orden ascendente. Debe validar la entrada, pero este código se omite para mayor claridad.

Aquí está la respuesta que se me ocurrió. Estoy escribiendo el código para que otras personas lo entiendan, por lo que soy bastante detallado con nombres de variables y comentarios.

Primero una función de ayuda rápida:

 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] 

Y luego el código real:

 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 

Ejecución de ejemplo:

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

devoluciones:

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

Salida:

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

Usando las listas de comprensión + numpy:
Con la función de diferencia numpy, las entradas de vectores de entrada consiguientes que su diferencia no es igual a una pueden ser identificadas. El inicio y el final del vector de entrada deben ser considerados.

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

Salida:

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

Nota: Se omitió la solicitud de que los números individuales deban ser tratados de manera diferente (devueltos como individuales, no rangos) Esto se puede lograr mediante un posterior procesamiento posterior de los resultados. Por lo general, esto hará que las cosas sean más complejas sin obtener ningún beneficio.

Una solución corta que funciona sin importaciones adicionales. Acepta cualquier iterable, ordena entradas sin ordenar y elimina elementos duplicados:

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

Ejemplo:

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

Esto es lo mismo que la solución de @dansalmo que encontré sorprendente, aunque un poco difícil de leer y aplicar (ya que no se ofrece como una función).

Tenga en cuenta que podría modificarse fácilmente para escupir rangos abiertos "tradicionales" [start, end) , por ejemplo, modificando la statement de retorno:

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

Copié esta respuesta de otra pregunta que estaba marcada como un duplicado de esta con la intención de hacerlo más fácil de encontrar (después de que acabo de buscar nuevamente este tema, encontré solo la pregunta aquí al principio y no me conformé con las respuestas). dado).