Me parece que lo primero que debe hacer es ordenar la lista. Entonces solo es cuestión de recorrerlo, recordar la duración de la secuencia actual y detectar cuándo ha terminado. Para ser honesto, yo sospecho que un bucle foreach simple va a ser la forma más simple de hacer eso - No puedo pensar de inmediato en ninguna manera maravillosamente limpia de LINQ de hacerlo. Ciertamente podría hacerlo en un bloque de iteradores si realmente quisiera, pero tenga en cuenta que ordenar la lista para comenzar significa que tiene un costo razonablemente "adelantado" de todos modos. Así que mi solución sería algo como esto:
var ordered = list.OrderBy(x => x);
int count = 0;
int firstItem = 0; // Irrelevant to start with
foreach (int x in ordered)
{
// First value in the ordered list: start of a sequence
if (count == 0)
{
firstItem = x;
count = 1;
}
// Skip duplicate values
else if (x == firstItem + count - 1)
{
// No need to do anything
}
// New value contributes to sequence
else if (x == firstItem + count)
{
count++;
}
// End of one sequence, start of another
else
{
if (count >= 3)
{
Console.WriteLine("Found sequence of length {0} starting at {1}",
count, firstItem);
}
count = 1;
firstItem = x;
}
}
if (count >= 3)
{
Console.WriteLine("Found sequence of length {0} starting at {1}",
count, firstItem);
}
EDIT: Bueno, he acaba de ocurrir una manera bastante más LINQ-ish de hacer las cosas. No tengo el tiempo para aplicar plenamente ahora, pero:
- Orden de la secuencia
- usar algo como
SelectWithPrevious (probablemente mejor llamado SelectConsecutive) para obtener pares consecutivos de elementos
- Use la sobrecarga de Seleccione cuál incluye el índice para obtener tuplas de (índice, actual, anterior)
- Filtre cualquier elemento donde (actual = anterior + 1) para llegar a cualquier lugar que cuente como comience de una secuencia (índice de caso especial = 0)
- Uso
SelectWithPrevious en el resultado para obtener el longitud de la secuencia entre dos puntos de partida (restar un índice a partir de la anterior)
- filtrar cualquier secuencia con longitud inferior a 3
I sospechoso se necesita concat int.MinValue en la secuencia ordenada, para garantizar que el elemento final se utiliza correctamente.
EDITAR: Bien, lo he implementado. Se trata de la manera más LINK que se me ocurre para hacer esto ... Utilicé valores nulos como valores "centinela" para forzar las secuencias de inicio y fin. Consulte los comentarios para obtener más detalles.
En general, no recomendaría esta solución. Es difícil darse vuelta, y aunque estoy razonablemente seguro de que es correcto, me tomó un tiempo pensar en posibles errores uno por uno, etc. Es un viaje interesante hacia lo que puede hacer con con LINQ ... y también lo que probablemente no deberías.
Ah, y tenga en cuenta que he enviado la parte de "longitud mínima de 3" a la persona que llama: cuando tiene una secuencia de tuplas como esta, es más limpio filtrarla por separado, IMO.
using System;
using System.Collections.Generic;
using System.Linq;
static class Extensions
{
public static IEnumerable<TResult> SelectConsecutive<TSource, TResult>
(this IEnumerable<TSource> source,
Func<TSource, TSource, TResult> selector)
{
using (IEnumerator<TSource> iterator = source.GetEnumerator())
{
if (!iterator.MoveNext())
{
yield break;
}
TSource prev = iterator.Current;
while (iterator.MoveNext())
{
TSource current = iterator.Current;
yield return selector(prev, current);
prev = current;
}
}
}
}
class Test
{
static void Main()
{
var list = new List<int> { 21,4,7,9,12,22,17,8,2,20,23 };
foreach (var sequence in FindSequences(list).Where(x => x.Item1 >= 3))
{
Console.WriteLine("Found sequence of length {0} starting at {1}",
sequence.Item1, sequence.Item2);
}
}
private static readonly int?[] End = { null };
// Each tuple in the returned sequence is (length, first element)
public static IEnumerable<Tuple<int, int>> FindSequences
(IEnumerable<int> input)
{
// Use null values at the start and end of the ordered sequence
// so that the first pair always starts a new sequence starting
// with the lowest actual element, and the final pair always
// starts a new one starting with null. That "sequence at the end"
// is used to compute the length of the *real* final element.
return End.Concat(input.OrderBy(x => x)
.Select(x => (int?) x))
.Concat(End)
// Work out consecutive pairs of items
.SelectConsecutive((x, y) => Tuple.Create(x, y))
// Remove duplicates
.Where(z => z.Item1 != z.Item2)
// Keep the index so we can tell sequence length
.Select((z, index) => new { z, index })
// Find sequence starting points
.Where(both => both.z.Item2 != both.z.Item1 + 1)
.SelectConsecutive((start1, start2) =>
Tuple.Create(start2.index - start1.index,
start1.z.Item2.Value));
}
}
¿Se permite que la lista tenga números duplicados? –
@Kyralessa No la lista nunca contendrá duplicados – Dve