Identificar grupos de números continuos en una lista.

94

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 era la mejor manera de hacer esto (particularmente si hay algo incorporado en Python).

Editar: Tenga en cuenta que originalmente olvidé mencionar que los números individuales deben devolverse como números individuales, no como rangos.

mikemaccana
fuente
3
¿Ese valor de retorno es una cadena?
Mark Byers
Idealmente, preferiría algo que use un tipo separado para rangos en lugar de números independientes.
mikemaccana

Respuestas:

53

more_itertools.consecutive_groups se agregó 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, creamos una función generadora 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 la fuente emula una receta clásica (como lo demostró @Nadia Alramli).

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

pylang
fuente
121

EDITAR 2: Para responder al nuevo requisito de 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 range o cualquier otra clase personalizada.


Los documentos de Python tienen una receta muy clara 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):i-x):
    print map(itemgetter(1), g)

Salida:

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

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

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

salida:

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

EDITAR: El ejemplo ya se explica 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 el dato fue: [2, 3, 4, 5, 12, 13, 14, 15, 16, 17] Entonces groupby(enumerate(data), lambda (i,x):i-x)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):i-x
)

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

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

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

Espero que esto lo haga más legible.

python 3 la versión puede ser útil para 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]))
Nadia Alramli
fuente
4
casi funciona en py3k, excepto que requiere lambda x:x[0]-x[1].
SilentGhost
¿Podría utilizar nombres de variables de varios caracteres? Para alguien que no esté familiarizado con map () o groupby (), los significados de kg, i y x no están claros.
mikemaccana
1
Esto se copió de la documentación de Python con los mismos nombres de variable. Cambié los nombres ahora.
Nadia Alramli
1
Deberá incrementar el segundo número en xrange / range porque no es inclusivo. En otras palabras [2,3,4,5] == xrange(2,6), no xrange(2,5). Puede valer la pena definir un nuevo tipo de datos de rango inclusivo.
IceArdor
10
Python 3 arroja un error de sintaxis en el primer ejemplo. Aquí están las primeras 2 líneas actualizadas para trabajar en python 3:for key, group in groupby(enumerate(data), lambda i: i[0] - i[1]): group = list(map(itemgetter(1), group))
derek73
16

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

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)]
truppo
fuente
Me gusta mucho esta respuesta porque es concisa pero legible. Sin embargo los números que están fuera de los rangos deben imprimirse como un solo dígito, no tuplas (como voy a formatear la salida y tienen diferentes requisitos de formato para los números individuales frente a rangos de números.
mikemaccana
4
La otra respuesta parecía hermosa e inteligente, pero esta es más comprensible para mí y le permitió a un principiante como yo expandirla de acuerdo con mis necesidades.
Benny
Podría usar una comprensión de lista para imprimir las tuplas sin rango como un solo dígito: print([i if i[0] != i[1] else i[0] for i in group(x)])
Nexus
14

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)]
SilentGhost
fuente
2
[j - i for i, j in enumerate(lst)]es inteligente :-)
Jochen Ritzel
9

Aquí hay algo que debería funcionar, sin necesidad de importar:

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
Andrea Ambu
fuente
6

Tenga en cuenta que el código que usa groupbyno 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]))
Mark Lawrence
fuente
3

Esto no usa una función estándar, solo escribe sobre 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 contenga solo números positivos en orden ascendente. Debe validar la entrada, pero este código se omite para mayor claridad.

Mark Byers
fuente
1

Aquí está la respuesta que se me ocurrió. Estoy escribiendo el código para que otras personas lo entiendan, así que soy bastante detallado con los 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]]
mikemaccana
fuente
>>> getranges([2, 12, 13])Salidas: [[12, 13]]. ¿Fue eso intencional?
SilentGhost
Sí, necesito corregir números individuales (según la mayoría de las respuestas en la página). Trabajando en eso ahora.
mikemaccana
En realidad, prefiero la respuesta de Nadia, groupby () parece la función estándar que quería.
mikemaccana
1
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]

fuente
1

El uso de groupbyy countde itertoolsnos da una breve solución. La idea es que, en una secuencia creciente, la diferencia entre el índice y el valor siga siendo la misma.

Para realizar un seguimiento del índice, podemos usar un itertools.count , que hace que el código sea más limpio al usar 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

Algunos resultados de muestra:

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

print(intervals([2, 3, 4, 5]))
# [[2, 5]]
Thierry Lathuille
fuente
0

Uso de listas de comprensión numpy +:
con la función numpy diff, se pueden identificar las entradas de vector de entrada consecuentes de que su diferencia no es igual a uno. Es necesario considerar el inicio y el final del vector de entrada.

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 se traten de manera diferente (devueltos como individuales, no como rangos). Esto se puede lograr procesando posteriormente los resultados. Por lo general, esto hará que las cosas sean más complejas sin obtener ningún beneficio.

Nir
fuente
0

Una solución corta que funciona sin importaciones adicionales. Acepta cualquier iterable, ordena las entradas sin clasificar y elimina los 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([])
[]

Esta es la misma que la solución de @ dansalmo que encontré increíble, aunque un poco difícil de leer y aplicar (ya que no se da como una función).

Tenga en cuenta que podría modificarse fácilmente para escupir rangos abiertos "tradicionales" [start, end), por ejemplo, alterando la declaración 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 hacerla 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 estoy satisfecho con las respuestas dado).

Coldfix
fuente
0

Las versiones de Mark Byers , Andrea Ambu , SilentGhost , Nadia Alramli y truppo son simples y rápidas. La versión 'truppo' me animó a escribir una versión que conserva el mismo comportamiento ágil mientras maneja tamaños de paso distintos de 1 (y enumera como elementos singletons que no se extienden más de 1 paso con un tamaño de paso dado). Se da aquí .

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