Agrupar enteros consecutivos y tolerar huecos de 1.

En Python, dada una lista de enteros ordenados, me gustaría agruparlos por valores consecutivos y tolerar huecos de 1.

Por ejemplo, dada una lista my_list :

 In [66]: my_list Out[66]: [0, 1, 2, 3, 5, 6, 10, 11, 15, 16, 18, 19, 20] 

Me gustaría la siguiente salida:

 [[0, 1, 2, 3, 5, 6], [10, 11], [15, 16, 18, 19, 20]] 

Ahora, si no tuviera que tolerar huecos de 1, podría aplicar la solución limpia que se explica aquí :

 import itertools import operator results = [] for k, g in itertools.groupby(enumerate(my_list), lambda (i,x):ix): group = map(operator.itemgetter(1), g) results.append(group) 

¿Hay alguna manera de incorporar mi requisito adicional en la solución anterior? Si no, ¿cuál es la mejor manera de abordar el problema?

En caso de duda siempre puedes escribir tu propio generador:

 def group_runs(li,tolerance=2): out = [] last = li[0] for x in li: if x-last > tolerance: yield out out = [] out.append(x) last = x yield out 

manifestación:

 list(group_runs(my_list)) Out[48]: [[0, 1, 2, 3, 5, 6], [10, 11], [15, 16, 18, 19, 20]] 

Numpy es una herramienta muy útil, y no muy difícil de aprender.

Este problema se puede solucionar en O(n) con una sola línea de código (excluyendo importaciones, datos y conversión a lista, si realmente lo necesita):

 from numpy import array, diff, where, split l= [0, 1, 2, 3, 5, 6, 10, 11, 15, 16, 18, 19, 20] result= split(l, where(diff(l)>2)[0]+1 ) print map(list, result) 

Más importante aún, el código es muy rápido si necesita procesar listas grandes, a diferencia de una solución de python puro

Recuerda, groupby en sí mismo, es bastante cojo. La fuerza de itertools.groupby es la clave. Para este problema en particular, necesita crear una clave apropiada con memoria (la clave sin estado no funcionará aquí).

Implementación

 class Key(object): def __init__(self, diff): self.diff, self.flag, self.prev = diff, [0,1], None def __call__(self, elem): if self.prev and abs(self.prev - elem) > self.diff: self.flag = self.flag[::-1] self.prev= elem return self.flag[0] 

Objeto

 [list(g) for k, g in groupby(my_list, key = Key(2))] [[0, 1, 2, 3, 5, 6], [10, 11], [15, 16, 18, 19, 20]] 

Cómo funciona

Cada vez que se debe crear una nueva sub-lista ( curr - prev > threshold ), se alterna una marca. Hay diferentes maneras de alternar una bandera

  • flag = 1; flag *= -1
  • flag = [0, 1 ]; flag = flag[::-1]
  • flag = 0; flag = 0 if flag else 1

Elige lo que tu corazón compite

Así que esto genera una clave acompañante junto con su lista

 [0, 1, 2, 3, 5, 6, 10, 11, 15, 16, 18, 19, 20] [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 , 0] <------> <------> Toggle flag Toggle flag 0 -> 1, as 1 -> 0, as 10 - 6 > 2 15 - 11 > 2 

Ahora, como itertools.groupby , agrupa los elementos consecutivos con la misma clave, todos los elementos con claves que tienen 0 s o 1 s consecutivos se agrupan

 [0, 1, 2, 3, 5, 6, 10, 11, 15, 16, 18, 19, 20] [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 , 0] [0, 1, 2, 3, 5, 6], [10, 11], [15, 16, 18, 19, 20] [0, 0, 0, 0, 0, 0], [1, 1], [0, 0, 0, 0 , 0] 

Y tu resultado final sería

 [0, 1, 2, 3, 5, 6], [10, 11], [15, 16, 18, 19, 20] 

Una solución O (nlogn) (asumiendo que la lista de entrada no está ordenada) es primero ordenar la lista que se le da, luego iterar a través de cada valor, creando un nuevo grupo siempre que la diferencia entre el valor actual y el valor anterior sea al menos 3.

Manifestación

 >>> my_list = [0, 1, 2, 3, 5, 6, 10, 11, 15, 16, 18, 19, 20] >>> my_list.sort() # if we can't assume the list is sorted beforehand >>> groups = [[my_list[0]]] # initialize with the first value in the list >>> for i, val in enumerate(my_list[1:]): ... if val - groups[-1][-1] > 2: ... groups.append( [val] ) # create a new group ... else: ... groups[-1].append( val ) # append to the most recent group ... >>> groups [[0, 1, 2, 3, 5, 6], [10, 11], [15, 16, 18, 19, 20]] 

Esto es lo que se me ocurrió. Hay un poco de inicialización detallada, pero hace el trabajo. =)

 output = [] prev = my_list[0] temp_list = [my_list[0]] for num in my_list[1:]: if num-2 > prev: output += [temp_list] temp_list = [num] else: temp_list.append(num) prev = num output.append(temp_list) print output # [[0, 1, 2, 3, 5, 6], [10, 11], [15, 16, 18, 19, 20]] 

Generalmente uso zip cuando quiero tratar con elementos consecutivos, y puedes usar la islice que quieras para evitar crear la porción de lista:

 from itertools import islice def group(lst, tol=1): """Group vals in sorted iterable lst, allow tol between consecutive vals.""" output = [[]] for current, next_ in zip(lst, islice(lst, 1, None)): output[-1].append(current) if next_ > current + tol + 1: output.append([]) output[-1].append(lst[-1]) return output 

Tenga en cuenta que en Python 2.x, debe usar itertools.izip para evitar la creación de la lista de 2 tuplas (current, next_) .