LINQ para encontrar series de números consecutivos

Tengo una lista de enteros. Quiero encontrar todas las ejecuciones de números consecutivos en esa lista, definidos por el índice y la longitud de inicio. Entonces, por ejemplo, para la lista de entrada de [1,2,3,5,7,8] , la salida sería [{1,3}, {5,1}, {7,2}] . Esto es bastante fácil de hacer usando un bucle, algo como esto (pseudocódigo no probado):

 for(i=1, i < maxNum; i++) { number = list[i]; previousNumber = list[i-1]; if(number - previousNumber == 1) { runLength++; } else { result.Add(startingNumber, runLength); runLength = 1; startingNumber = number; } } 

Pero pensé que sería posible hacerlo con LINQ. Alguna idea de como hacer eso?

Una forma lógica puede ser escribir un método de extensión GroupWhile como a continuación ( GroupWhile todas las comprobaciones, no optimizado para que lo entienda fácilmente).

 int[] list = new int[] { 1, 2, 3, 5, 7, 8 }; var result = list.GroupWhile((x, y) => y - x == 1) .Select(x => new {i = x.First(), len = x.Count() }) .ToList(); 

 public static IEnumerable> GroupWhile(this IEnumerable seq, Func condition) { T prev = seq.First(); List list = new List() { prev }; foreach(T item in seq.Skip(1)) { if(condition(prev,item)==false) { yield return list; list = new List(); } list.Add(item); prev = item; } yield return list; } 

TODO: use IGrouping 🙂

Esto parece un enfoque razonable:

  1. Zip la lista original con un Range , por lo que cada elemento se tupla con su índice
  2. Seleccione aquellos elementos cuya lista predecesora no sea su predecesora natural
  3. Convierta en matriz y guárdela en variable temporal (para facilitar el último paso).
  4. Deduce la longitud de los subarrays de los índices. Para el último artículo, es la diferencia con la longitud de la lista original. Para los otros artículos, es la diferencia con el siguiente índice.
 var list = new int[] { 1, 2, 3, 5, 7, 8 }; var filtered = list.Zip(Enumerable.Range(0, list.Length), Tuple.Create) .Where((x, i) => i == 0 || list[i - 1] != x.Item1 - 1).ToArray(); var result = filtered.Select((x, i) => i == filtered.Length - 1 ? Tuple.Create(x.Item1, list.Length - x.Item2) : Tuple.Create(x.Item1, filtered[i + 1].Item2 - x.Item2)); foreach (var t in result) { Console.WriteLine(t); } 

Esto resulta en

 (1, 3) (5, 1) (7, 2) 

¿Alguien preguntó para calzar una solución en una consulta LINQ de dudosa legibilidad?

 var serieses = input.Aggregate( new List>(), (l, i) => { var last = l.LastOrDefault(); if (last == null || last.Item1 + last.Item2 != i) { l.Add(new Tuple(i, 1)); } else if (last.Item1 + last.Item2 == i) { l.RemoveAt(l.Count - 1); l.Add(new Tuple(last.Item1, last.Item2 + 1)); } return l; }, l => l); 

No hay un método de extensión fuera de caja, pero puede crear su propio:

 public static class LinqUtils{ public class ConsecutiveGroup { public T Left { get; internal set; } public T Right { get; internal set; } public long Count { get; internal set; } } public static IEnumerable> ConsecutiveCounts(this IEnumerable src, Func consecutive) { ConsecutiveGroup current = null; foreach (var s in src) { if (current==null) { current = new ConsecutiveGroup { Left = s, Right = s, Count = 1 }; continue; } if(consecutive(current.Right, s)) { current.Right = s; current.Count += 1; continue; } yield return current; current = new ConsecutiveGroup { Left = s, Right = s, Count = 1 }; } if (current!=null) { yield return current; } } } [TestFixture] public static class LinqUtilsTests { [Test] public void TestConsecutiveCounts() { var src = new[] {1,2,3,5,7,8}; var expected = new[] { Tuple.Create(1, 3), Tuple.Create(5, 1), Tuple.Create(7, 2) }; var result = src .ConsecutiveCounts((prev, current) => current == (prev + 1)) .Select(c=>Tuple.Create(c.Left, c.Count)); Assert.IsTrue(expected.SequenceEqual(result)); } } 

Necesita una forma de escanear la secuencia, acumular resultados y luego agruparlos. Entonces, primero un método de extensión de Scan simple (similar a Aggregate pero arroja resultados intermedios) (existe un método de Scan para IObservable pero no para IEnumerable ):

 public static IEnumerable Scan(this IEnumerable input, Func next, U state) { yield return state; foreach (var item in input) { state = next(state, item); yield return state; } } 

Y usando este método y el método de extensión Zip , haga lo siguiente:

 var ints = new[] { 1, 2, 3, 5, 7, 8, 10 }; var result = ints // Zip the list with itself shifted 1 to the left (add dummy value at the end) // and calculate the difference between each consecutive value. .Zip(ints .Skip(1) .Concat(new[] { int.MaxValue }), (i0, i1) => new { i = i0, diff = i1 - i0 }) // Reverse because it's far easier keeping track of the group we're at .Reverse() // Scan through the list, assigning an incremental group number to each // consecutive sequence .Scan((state, z) => state == null ? Tuple.Create(zi, z.diff, 0) : Tuple.Create(zi, z.diff, z.diff > 1 ? state.Item3 + 1 : state.Item3), (Tuple) null) // <-- dummy starting state. // Skip the dummy starting state we started the scan with .Skip(1) // Reverse back .Reverse() // Group by the group numbers we assigned during the scan .GroupBy(t => t.Item3, (i, l) => new { l.First().Item1, l = l.Count() });