c# - Detección de la secuencia de al menos 3 números secuenciales de una lista dada
logic sequences (12)
Tengo una lista de números, por ejemplo, 21,4,7,9,12,22,17,8,2,20,23
Quiero poder seleccionar secuencias de números secuenciales (mínimo 3 elementos de longitud), por lo que del ejemplo anterior sería 7,8,9 y 20,21,22,23.
He jugado un poco con algunas funciones desagradables pero me estoy preguntando si hay una forma clara de LINQ-ish para hacerlo.
¿Alguna sugerencia?
ACTUALIZAR:
Muchas gracias por todas las respuestas, muchas gracias. Actualmente estoy jugando con todos ellos para ver cuál se integraría mejor en nuestro proyecto.
¿Qué hay de ordenar la matriz y luego crear otra matriz que sea la diferencia entre cada elemento del anterior?
sortedArray = 8, 9, 10, 21, 22, 23, 24, 27, 30, 31, 32
diffArray = 1, 1, 11, 1, 1, 1, 3, 3, 1, 1 Ahora iterar a través de la matriz de diferencia; si la diferencia es igual a 1, aumente la cuenta de una variable, sequenceLength, en 1. Si la diferencia es> 1, verifique la secuenciaLength si es> = 2, entonces tiene una secuencia de al menos 3 elementos consecutivos. Luego restablezca la secuencia de secuencia a 0 y continúe su bucle en la matriz de diferencias.
Aquí es cómo resolver el problema de una manera "LINQish":
int[] arr = new int[]{ 21, 4, 7, 9, 12, 22, 17, 8, 2, 20, 23 };
IOrderedEnumerable<int> sorted = arr.OrderBy(x => x);
int cnt = sorted.Count();
int[] sortedArr = sorted.ToArray();
IEnumerable<int> selected = sortedArr.Where((x, idx) =>
idx <= cnt - 3 && sortedArr[idx + 1] == x + 1 && sortedArr[idx + 2] == x + 2);
IEnumerable<int> result = selected.SelectMany(x => new int[] { x, x + 1, x + 2 }).Distinct();
Console.WriteLine(string.Join(",", result.Select(x=>x.ToString()).ToArray()));
Debido a la copia y reconstrucción de matrices, esta solución, por supuesto, no es tan eficiente como la solución tradicional con bucles.
Aquí está mi LINQ-y asumir el problema:
static IEnumerable<IEnumerable<int>>
ConsecutiveSequences(this IEnumerable<int> input, int minLength = 3)
{
int order = 0;
var inorder = new SortedSet<int>(input);
return from item in new[] { new { order = 0, val = inorder.First() } }
.Concat(
inorder.Zip(inorder.Skip(1), (x, val) =>
new { order = x + 1 == val ? order : ++order, val }))
group item.val by item.order into list
where list.Count() >= minLength
select list;
}
- no utiliza bucles explícitos, pero aún debería ser O (n lg n)
- utiliza
SortedSetlugar de.OrderBy().Distinct() - combina elemento consecutivo con
list.Zip(list.Skip(1))
Aquí está mi oportunidad:
public static class SequenceDetector
{
public static IEnumerable<IEnumerable<T>> DetectSequenceWhere<T>(this IEnumerable<T> sequence, Func<T, T, bool> inSequenceSelector)
{
List<T> subsequence = null;
// We can only have a sequence with 2 or more items
T last = sequence.FirstOrDefault();
foreach (var item in sequence.Skip(1))
{
if (inSequenceSelector(last, item))
{
// These form part of a sequence
if (subsequence == null)
{
subsequence = new List<T>();
subsequence.Add(last);
}
subsequence.Add(item);
}
else if (subsequence != null)
{
// We have a previous seq to return
yield return subsequence;
subsequence = null;
}
last = item;
}
if (subsequence != null)
{
// Return any trailing seq
yield return subsequence;
}
}
}
public class test
{
public static void run()
{
var list = new List<int> { 21, 4, 7, 9, 12, 22, 17, 8, 2, 20, 23 };
foreach (var subsequence in list
.OrderBy(i => i)
.Distinct()
.DetectSequenceWhere((first, second) => first + 1 == second)
.Where(seq => seq.Count() >= 3))
{
Console.WriteLine("Found subsequence {0}",
string.Join(", ", subsequence.Select(i => i.ToString()).ToArray()));
}
}
}
Esto devuelve los elementos específicos que forman las subsecuencias y permite cualquier tipo de elemento y cualquier definición de criterios, siempre que se pueda determinar comparando elementos adyacentes.
Aquí hay una solución que encontré en F #, debería ser bastante fácil traducir esto en una consulta de C # LINQ, ya que fold es bastante equivalente al operador agregado de LINQ.
#light
let nums = [21;4;7;9;12;22;17;8;2;20;23]
let scanFunc (mainSeqLength, mainCounter, lastNum:int, subSequenceCounter:int, subSequence:''a list, foundSequences:''a list list) (num:''a) =
(mainSeqLength, mainCounter + 1,
num,
(if num <> lastNum + 1 then 1 else subSequenceCounter+1),
(if num <> lastNum + 1 then [num] else subSequence@[num]),
if subSequenceCounter >= 3 then
if mainSeqLength = mainCounter+1
then foundSequences @ [subSequence@[num]]
elif num <> lastNum + 1
then foundSequences @ [subSequence]
else foundSequences
else foundSequences)
let subSequences = nums |> Seq.sort |> Seq.fold scanFunc (nums |> Seq.length, 0, 0, 0, [], []) |> fun (_,_,_,_,_,results) -> results
Aquí hay una solución que usa un Diccionario en lugar de una ordenación ... Agrega los elementos a un Diccionario y luego, para cada valor, aumenta arriba y abajo para encontrar la secuencia más larga.
No es estrictamente LINQ, aunque hace uso de algunas funciones de LINQ, y creo que es más legible que una solución LINQ pura.
static void Main(string[] args)
{
var items = new[] { -1, 0, 1, 21, -2, 4, 7, 9, 12, 22, 17, 8, 2, 20, 23 };
IEnumerable<IEnumerable<int>> sequences = FindSequences(items, 3);
foreach (var sequence in sequences)
{ //print results to consol
Console.Out.WriteLine(sequence.Select(num => num.ToString()).Aggregate((a, b) => a + "," + b));
}
Console.ReadLine();
}
private static IEnumerable<IEnumerable<int>> FindSequences(IEnumerable<int> items, int minSequenceLength)
{
//Convert item list to dictionary
var itemDict = new Dictionary<int, int>();
foreach (int val in items)
{
itemDict[val] = val;
}
var allSequences = new List<List<int>>();
//for each val in items, find longest sequence including that value
foreach (var item in items)
{
var sequence = FindLongestSequenceIncludingValue(itemDict, item);
allSequences.Add(sequence);
//remove items from dict to prevent duplicate sequences
sequence.ForEach(i => itemDict.Remove(i));
}
//return only sequences longer than 3
return allSequences.Where(sequence => sequence.Count >= minSequenceLength).ToList();
}
//Find sequence around start param value
private static List<int> FindLongestSequenceIncludingValue(Dictionary<int, int> itemDict, int value)
{
var result = new List<int>();
//check if num exists in dictionary
if (!itemDict.ContainsKey(value))
return result;
//initialize sequence list
result.Add(value);
//find values greater than starting value
//and add to end of sequence
var indexUp = value + 1;
while (itemDict.ContainsKey(indexUp))
{
result.Add(itemDict[indexUp]);
indexUp++;
}
//find values lower than starting value
//and add to start of sequence
var indexDown = value - 1;
while (itemDict.ContainsKey(indexDown))
{
result.Insert(0, itemDict[indexDown]);
indexDown--;
}
return result;
}
Creo que mi solución es más elegante y simple, y por lo tanto más fácil de verificar como correcta:
/// <summary>Returns a collection containing all consecutive sequences of
/// integers in the input collection.</summary>
/// <param name="input">The collection of integers in which to find
/// consecutive sequences.</param>
/// <param name="minLength">Minimum length that a sequence should have
/// to be returned.</param>
static IEnumerable<IEnumerable<int>> ConsecutiveSequences(
IEnumerable<int> input, int minLength = 1)
{
var results = new List<List<int>>();
foreach (var i in input.OrderBy(x => x))
{
var existing = results.FirstOrDefault(lst => lst.Last() + 1 == i);
if (existing == null)
results.Add(new List<int> { i });
else
existing.Add(i);
}
return minLength <= 1 ? results :
results.Where(lst => lst.Count >= minLength);
}
Beneficios sobre las otras soluciones:
- Puede encontrar secuencias que se superponen.
- Es adecuadamente reutilizable y documentado.
- No he encontrado ningún error ;-)
Las soluciones de Jon Skeet / Timwi son el camino a seguir.
Por diversión, aquí hay una consulta LINQ que hace el trabajo ( muy ineficientemente):
var sequences = input.Distinct()
.GroupBy(num => Enumerable.Range(num, int.MaxValue - num + 1)
.TakeWhile(input.Contains)
.Last()) //use the last member of the consecutive sequence as the key
.Where(seq => seq.Count() >= 3)
.Select(seq => seq.OrderBy(num => num)); // not necessary unless ordering is desirable inside each sequence.
El rendimiento de la consulta se puede mejorar ligeramente cargando la entrada en un HashSet (para mejorar Contains ), pero eso no producirá una solución que sea casi eficiente.
El único error que conozco es la posibilidad de un desbordamiento aritmético si la secuencia contiene números negativos de gran magnitud (no podemos representar el parámetro de count para el Range ). Esto sería fácil de solucionar con un método de extensión static IEnumerable<int> To(this int start, int end) personalizado static IEnumerable<int> To(this int start, int end) personalizado. Si alguien puede pensar en alguna otra técnica simple de esquivar el desbordamiento, hágamelo saber.
EDITAR: Aquí hay una variante ligeramente más detallada (pero igualmente ineficiente) sin el problema de desbordamiento.
var sequences = input.GroupBy(num => input.Where(candidate => candidate >= num)
.OrderBy(candidate => candidate)
.TakeWhile((candidate, index) => candidate == num + index)
.Last())
.Where(seq => seq.Count() >= 3)
.Select(seq => seq.OrderBy(num => num));
Linq no es la solución para todo, a veces eres mejor con un simple bucle. Aquí hay una solución, con solo un poco de Linq para ordenar las secuencias originales y filtrar los resultados
void Main()
{
var numbers = new[] { 21,4,7,9,12,22,17,8,2,20,23 };
var sequences =
GetSequences(numbers, (prev, curr) => curr == prev + 1);
.Where(s => s.Count() >= 3);
sequences.Dump();
}
public static IEnumerable<IEnumerable<T>> GetSequences<T>(
IEnumerable<T> source,
Func<T, T, bool> areConsecutive)
{
bool first = true;
T prev = default(T);
List<T> seq = new List<T>();
foreach (var i in source.OrderBy(i => i))
{
if (!first && !areConsecutive(prev, i))
{
yield return seq.ToArray();
seq.Clear();
}
first = false;
seq.Add(i);
prev = i;
}
if (seq.Any())
yield return seq.ToArray();
}
Me parece que lo primero que debes hacer es ordenar la lista. Entonces solo es cuestión de recorrerla, recordar la longitud de su secuencia actual y detectar cuándo ha terminado. Para ser honesto, sospecho que un simple bucle de foreach será la forma más sencilla de hacerlo; no puedo pensar de inmediato en ninguna forma de LINQ maravillosamente limpia. Ciertamente, podría hacerlo en un bloque de iteradores si realmente quisiera, pero tenga en cuenta que ordenar la lista para comenzar significa que, de todos modos, tiene un costo "inicial" razonable. Entonces mi solución se vería así:
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: De acuerdo, acabo de pensar en una forma de hacer las cosas algo más LINQ-ish. No tengo tiempo para implementarlo completamente ahora, pero:
- Ordenar la secuencia
- Use algo como
SelectWithPrevious(probablemente mejor llamadoSelectConsecutive) para obtener pares de elementos consecutivos - Utilice la sobrecarga de Seleccionar, que incluye el índice para obtener tuplas de (índice, actual, anterior)
- Filtre los elementos donde (actual = anterior + 1) para llegar a cualquier lugar que cuente como el inicio de una secuencia (índice de casos especiales = 0)
- Use
SelectWithPreviousen el resultado para obtener la longitud de la secuencia entre dos puntos de inicio (reste un índice del anterior) - Filtra cualquier secuencia con longitud menor a 3
Sospecho que necesita concat int.MinValue en la secuencia ordenada, para garantizar que el elemento final se utiliza correctamente.
EDIT: Está bien, he implementado esto. Se trata de la forma en que puedo pensar en LINQiest para hacer esto ... Utilicé valores nulos como valores "centinela" para forzar las secuencias de inicio y finalización - vea los comentarios para obtener más detalles.
En general, no recomendaría esta solución. Es difícil que te vuelvas loco, y aunque estoy razonablemente seguro de que es correcto, me tomó un tiempo pensar en posibles errores off-by-one, etc. Es un viaje interesante a lo que puedes hacer con LINQ ... y también lo que probablemente no deberías
Ah, y tenga en cuenta que he subido 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, OMI.
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));
}
}
No 100% Linq pero aquí hay una variante genérica:
static IEnumerable<IEnumerable<TItem>> GetSequences<TItem>(
int minSequenceLength,
Func<TItem, TItem, bool> areSequential,
IEnumerable<TItem> items)
where TItem : IComparable<TItem>
{
items = items
.OrderBy(n => n)
.Distinct().ToArray();
var lastSelected = default(TItem);
var sequences =
from startItem in items
where startItem.Equals(items.First())
|| startItem.CompareTo(lastSelected) > 0
let sequence =
from item in items
where item.Equals(startItem) || areSequential(lastSelected, item)
select (lastSelected = item)
where sequence.Count() >= minSequenceLength
select sequence;
return sequences;
}
static void UsageInt()
{
var sequences = GetSequences(
3,
(a, b) => a + 1 == b,
new[] { 21, 4, 7, 9, 12, 22, 17, 8, 2, 20, 23 });
foreach (var sequence in sequences)
Console.WriteLine(string.Join(", ", sequence.ToArray()));
}
static void UsageChar()
{
var list = new List<char>(
"abcdefghijklmnopqrstuvwxyz".ToCharArray());
var sequences = GetSequences(
3,
(a, b) => (list.IndexOf(a) + 1 == list.IndexOf(b)),
"PleaseBeGentleWithMe".ToLower().ToCharArray());
foreach (var sequence in sequences)
Console.WriteLine(string.Join(", ", sequence.ToArray()));
}
Pensé en lo mismo que Jon : para representar un rango de enteros consecutivos, ¡todo lo que realmente necesitas son dos enteros miserables! Así que empezaría allí:
struct Range : IEnumerable<int>
{
readonly int _start;
readonly int _count;
public Range(int start, int count)
{
_start = start;
_count = count;
}
public int Start
{
get { return _start; }
}
public int Count
{
get { return _count; }
}
public int End
{
get { return _start + _count - 1; }
}
public IEnumerator<int> GetEnumerator()
{
for (int i = 0; i < _count; ++i)
{
yield return _start + i;
}
}
// Heck, why not?
public static Range operator +(Range x, int y)
{
return new Range(x.Start, x.Count + y);
}
// skipping the explicit IEnumerable.GetEnumerator implementation
}
Desde allí, puede escribir un método estático para devolver un grupo de estos valores de Range correspondientes a los números consecutivos de su secuencia.
static IEnumerable<Range> FindRanges(IEnumerable<int> source, int minCount)
{
// throw exceptions on invalid arguments, maybe...
var ordered = source.OrderBy(x => x);
Range r = default(Range);
foreach (int value in ordered)
{
// In "real" code I would''ve overridden the Equals method
// and overloaded the == operator to write something like
// if (r == Range.Empty) here... but this works well enough
// for now, since the only time r.Count will be 0 is on the
// first item.
if (r.Count == 0)
{
r = new Range(value, 1);
continue;
}
if (value == r.End)
{
// skip duplicates
continue;
}
else if (value == r.End + 1)
{
// "append" consecutive values to the range
r += 1;
}
else
{
// return what we''ve got so far
if (r.Count >= minCount)
{
yield return r;
}
// start over
r = new Range(value, 1);
}
}
// return whatever we ended up with
if (r.Count >= minCount)
{
yield return r;
}
}
Manifestación:
int[] numbers = new[] { 21, 4, 7, 9, 12, 22, 17, 8, 2, 20, 23 };
foreach (Range r in FindConsecutiveRanges(numbers, 3))
{
// Using .NET 3.5 here, don''t have the much nicer string.Join overloads.
Console.WriteLine(string.Join(", ", r.Select(x => x.ToString()).ToArray()));
}
Salida:
7, 8, 9 20, 21, 22, 23