Identificar grupos de diferentes números continuos en una lista

En esta otra publicación de SO , un usuario de Python preguntó cómo agrupar números continuos de modo que cualquier secuencia pudiera representarse simplemente por su inicio / fin y los rezagados se mostraran como elementos individuales. La respuesta aceptada funciona shinymente para secuencias continuas.

Necesito poder adaptar una solución similar, pero para una secuencia de números que tienen incrementos potencialmente variables (no siempre). Idealmente, cómo represento eso también incluirá el incremento (para que sepan si fue cada 3, 4, 5, nth)

Haciendo referencia a la pregunta original, el usuario solicitó la siguiente entrada / salida

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

Lo que me gustaría es lo siguiente (Nota: escribí una tupla como salida para mayor claridad pero se preferiría xrange usando su variable de paso):

 [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20] # input [(2,5,1), (12,17,1), 20] # note, the last element in the tuple would be the step value 

Y también podría manejar la siguiente entrada

 [2, 4, 6, 8, 12, 13, 14, 15, 16, 17, 20] # input [(2,8,2), (12,17,1), 20] # note, the last element in the tuple would be the increment 

Sé que xrange() admite un paso, por lo que incluso es posible utilizar una variante de la respuesta del otro usuario. Intenté hacer algunas ediciones basadas en lo que escribieron en la explicación, pero no pude obtener el resultado que estaba buscando.

Para cualquier persona que no quiera hacer clic en el enlace original, el código que originalmente publicó Nadia Alramli es:

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

Puede crear un iterador para ayudar a agrupar e intentar extraer el siguiente elemento del siguiente grupo, que será el final del grupo anterior:

 def ranges(lst): it = iter(lst) next(it) # move to second element for comparison grps = groupby(lst, key=lambda x: (x - next(it, -float("inf")))) for k, v in grps: i = next(v) try: step = next(v) - i # catches single element v or gives us a step nxt = list(next(grps)[1]) yield xrange(i, nxt.pop(0), step) # outliers or another group if nxt: yield nxt[0] if len(nxt) == 1 else xrange(nxt[0], next(next(grps)[1]), nxt[1] - nxt[0]) except StopIteration: yield i # no seq 

que te dan:

 In [2]: l1 = [2, 3, 4, 5, 8, 10, 12, 14, 13, 14, 15, 16, 17, 20, 21] In [3]: l2 = [2, 4, 6, 8, 12, 13, 14, 15, 16, 17, 20] In [4]: l3 = [13, 14, 15, 16, 17, 18] In [5]: s1 = [i + 10 for i in xrange(0, 11, 2)] In [6]: s2 = [30] In [7]: s3 = [i + 40 for i in xrange(45)] In [8]: l4 = s1 + s2 + s3 In [9]: l5 = [1, 2, 5, 6, 9, 10] In [10]: l6 = {1, 2, 3, 5, 6, 9, 10, 13, 19, 21, 22, 23, 24} In [11]: In [11]: for l in (l1, l2, l3, l4, l5, l6): ....: print(list(ranges(l))) ....: [xrange(2, 5), xrange(8, 14, 2), xrange(13, 17), 20, 21] [xrange(2, 8, 2), xrange(12, 17), 20] [xrange(13, 18)] [xrange(10, 20, 2), 30, xrange(40, 84)] [1, 2, 5, 6, 9, 10] [xrange(1, 3), 5, 6, 9, 10, 13, 19, xrange(21, 24)] 

Cuando el paso es 1 , no se incluye en la salida xrange.

La receta de pares de itertools es una forma de resolver el problema. Aplicado con itertools.groupby , se pueden itertools.groupby grupos de pares cuyas diferencias matemáticas son equivalentes. Los primeros y últimos elementos de cada grupo se seleccionan para grupos de múltiples elementos o el último elemento se selecciona para grupos singleton:

 from itertools import groupby, tee, izip def pairwise(iterable): "s -> (s0,s1), (s1,s2), (s2, s3), ..." a, b = tee(iterable) next(b, None) return izip(a, b) def grouper(lst): result = [] for k, g in groupby(pairwise(lst), key=lambda x: x[1] - x[0]): g = list(g) if len(g) > 1: try: if g[0][0] == result[-1]: del result[-1] elif g[0][0] == result[-1][1]: g = g[1:] # patch for duplicate start and/or end except (IndexError, TypeError): pass result.append((g[0][0], g[-1][-1], k)) else: result.append(g[0][-1]) if result else result.append(g[0]) return result 

Prueba: input -> grouper(lst) -> output

 Input: [2, 3, 4, 5, 12, 13, 14, 15, 16, 17, 20] Output: [(2, 5, 1), (12, 17, 1), 20] Input: [2, 4, 6, 8, 12, 13, 14, 15, 16, 17, 20] Output: [(2, 8, 2), (12, 17, 1), 20] Input: [2, 4, 6, 8, 12, 12.4, 12.9, 13, 14, 15, 16, 17, 20] Output: [(2, 8, 2), 12, 12.4, 12.9, (13, 17, 1), 20] # 12 does not appear in the second group 

Actualización : ( parche para valores de inicio y / o final duplicados )

 s1 = [i + 10 for i in xrange(0, 11, 2)]; s2 = [30]; s3 = [i + 40 for i in xrange(45)] Input: s1+s2+s3 Output: [(10, 20, 2), (30, 40, 10), (41, 84, 1)] # to make 30 appear as an entry instead of a group change main if condition to len(g) > 2 Input: s1+s2+s3 Output: [(10, 20, 2), 30, (41, 84, 1)] Input: [2, 4, 6, 8, 10, 12, 13, 14, 15, 16, 17, 20] Output: [(2, 12, 2), (13, 17, 1), 20] 

Aquí hay una respuesta rápidamente escrita (y extremadamente fea):

 def test(inArr): arr=inArr[:] #copy, unnecessary if we use index in a smart way result = [] while len(arr)>1: #as long as there can be an arithmetic progression x=[arr[0],arr[1]] #take first two arr=arr[2:] #remove from array step=x[1]-x[0] while len(arr)>0 and x[1]+step==arr[0]: #check if the next value in array is part of progression too x[1]+=step #add it arr=arr[1:] result.append((x[0],x[1],step)) #append progression to result if len(arr)==1: result.append(arr[0]) return result print test([2, 4, 6, 8, 12, 13, 14, 15, 16, 17, 20]) 

Esto devuelve [(2, 8, 2), (12, 17, 1), 20]

Lento, ya que copia una lista y elimina elementos de ella.

Solo encuentra progresiones completas, y solo en arreglos ordenados.

En resumen, es una mierda, pero debería funcionar;)

Hay otras formas (más frescas, más pythonic) de hacer esto, por ejemplo, puede convertir su lista en un conjunto, seguir eliminando dos elementos, calcular su progresión aritmética e intersectarse con el conjunto.

También puede reutilizar la respuesta que proporcionó para verificar ciertos tamaños de paso. p.ej:

 ranges = [] step_size=2 for key, group in groupby(enumerate(data), lambda (index, item): step_size*index - item): group = map(itemgetter(1), group) if len(group) > 1: ranges.append(xrange(group[0], group[-1])) else: ranges.append(group[0]) 

Lo que encuentra cada grupo con un tamaño de paso de 2 , pero solo aquellos.