conseguir siguiente entero disponible utilizando LINQ

Question

Decir que tengo una lista de números enteros:

List<int> myInts = new List<int>() {1,2,3,5,8,13,21}; 

me gustaría obtener el siguiente número entero disponibles, clasificadas por el aumento de número entero. No es el último o el más alto, pero en este caso el siguiente entero que no está en esta lista. En este caso, el número es 4.

¿Hay alguna declaración LINQ que me dé esto? Como en:

var nextAvailable = myInts.SomeCoolLinqMethod(); 

Edit: Crap. Dije que la respuesta debería ser 2 pero quise decir 4. ¡Me disculpo por eso!

Por ejemplo: imagine que es responsable de entregar los ID de proceso. Desea obtener la lista de ID de procesos actuales y emitir una próxima, pero la siguiente no debe ser solo el valor más alto más uno. Más bien, debería ser el siguiente disponible de una lista ordenada de ID de proceso. Puede obtener el siguiente disponible comenzando por el más alto, en realidad no importa.

Answer 1

public static class IntExtensions 
{ 
    public static int? SomeCoolLinqMethod(this IEnumerable<int> ints) 
    { 
     int counter = ints.Count() > 0 ? ints.First() : -1; 

     while (counter < int.MaxValue) 
     { 
      if (!ints.Contains(++counter)) return counter; 
     } 

     return null; 
    } 
} 

Uso:

var nextAvailable = myInts.SomeCoolLinqMethod(); 

Answer 2

autorización, aquí es la solución que se me ocurrió que funciona para mí.

var nextAvailableInteger = Enumerable.Range(myInts.Min(),myInts.Max()).FirstOrDefault(r=> !myInts.Contains(r)); 

Si alguien tiene una solución más elegante, me gustaría aceptarla. Pero por ahora, esto es lo que pongo en mi código y sigo adelante.

Editar: esto es lo que implementé después de la sugerencia de Kevin de agregar un método de extensión. Y esa fue la verdadera respuesta, que ninguna extensión de LINQ sería suficiente, así que tiene más sentido agregar la mía. Eso es realmente lo que estaba buscando.

public static int NextAvailableInteger(this IEnumerable<int> ints) 
{ 
    return NextAvailableInteger(ints, 1); // by default we use one 
} 
public static int NextAvailableInteger(this IEnumerable<int> ints, int defaultValue) 
{ 
    if (ints == null || ints.Count() == 0) return defaultValue; 

    var ordered = ints.OrderBy(v => v); 
    int counter = ints.Min(); 
    int max = ints.Max(); 

    while (counter < max) 
    { 
     if (!ordered.Contains(++counter)) return counter; 
    } 
    return (++counter); 
} 

Answer 3

Ésta será bastante eficiente:

static int Next(this IEnumerable<int> source) 
{ 
    int? last = null; 
    foreach (var next in source.OrderBy(_ => _)) 
    { 
     if (last.HasValue && last.Value + 1 != next) 
     { 
      return last.Value + 1; 
     } 

     last = next; 
    } 

    return last.HasValue ? last.Value + 1 : Int32.MaxValue; 
} 

Answer 4

La respuesta proporcionada por @ Kevin tiene un perfil de rendimiento indeseable. La lógica accederá a la secuencia fuente en numerosas ocasiones: una para la llamada .Count, una para la llamada .FirstOrDefault, y una para cada llamada .Contains. Si la instancia IEnumerable<int> es una secuencia diferida, como el resultado de una llamada .Select, esto causará al menos 2 cálculos de la secuencia, junto con una vez para cada número. Incluso si pasa una lista al método, posiblemente revisará toda la lista para cada número verificado. Imagine ejecutarlo en la secuencia { 1, 1000000 } y puede ver cómo no funcionaría bien.

LINQ se esfuerza por iterar secuencias de origen no más de una vez. Esto es posible en general y puede tener un gran impacto en el rendimiento de su código. Debajo hay un método de extensión que repetirá la secuencia exactamente una vez. Lo hace mediante la búsqueda de la diferencia entre cada par sucesivo, a continuación, añade 1 al primer número inferior que es más de 1 lejos de la siguiente número:

public static int? FirstMissing(this IEnumerable<int> numbers) 
{ 
    int? priorNumber = null; 

    foreach(var number in numbers.OrderBy(n => n)) 
    { 
     var difference = number - priorNumber; 

     if(difference != null && difference > 1) 
     { 
      return priorNumber + 1; 
     } 

     priorNumber = number; 
    } 

    return priorNumber == null ? (int?) null : priorNumber + 1; 
} 

Dado que este método de extensión se puede llamar en cualquier secuencia arbitraria de enteros, nos aseguramos de pedirlos antes de iterar. Luego calculamos la diferencia entre el número actual y el número anterior.Si este es el primer número de la lista, priorNumber será nulo y, por lo tanto, difference será nulo. Si este no es el primer número de la lista, verificamos si la diferencia con el número anterior es exactamente 1. Si no, sabemos que hay un espacio y podemos agregar 1 al número anterior.

Puede ajustar la declaración de devolución para manejar secuencias con 0 o 1 elementos como mejor le parezca; Elijo devolver nulo para secuencias vacías y n + 1 para la secuencia { n }.

Answer 5

Veo una gran cantidad de respuestas que escribir un método de extensión personalizada, pero es posible resolver este problema con los métodos de extensión LINQ estándar y la estática de clase Enumerable:

List<int> myInts = new List<int>() {1,2,3,5,8,13,21}; 

// This will set firstAvailable to 4. 
int firstAvailable = Enumerable.Range(1, Int32.MaxValue).Except(myInts).First(); 

Answer 6

No estoy seguro si esto califica como un método de LINQ fresco, pero el uso de la combinación externa izquierda idea de This SO Answer

var thelist = new List<int> {1,2,3,4,5,100,101}; 

var nextAvailable = (from curr in thelist 
        join next in thelist 
         on curr + 1 equals next into g 
        from newlist in g.DefaultIfEmpty() 
        where !g.Any() 
        orderby curr 
        select curr + 1).First(); 

Esto pone el procesamiento del lado del servidor SQL si está utilizando LINQ to SQL, y le permite no tiene que tirar de las listas de ID desde el servidor a memo ry.