ottenere successivo numero intero a disposizione utilizzando LINQ

Question

dire che ho un elenco di numeri interi:

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

Vorrei ottenere il successivo numero intero a disposizione, ordinate per aumentando intero. Non l'ultimo o il più alto, ma in questo caso il prossimo numero intero che non è in questa lista. In questo caso il numero è 4.

Esiste una dichiarazione LINQ che potrebbe darmi questo? Come in:

var nextAvailable = myInts.SomeCoolLinqMethod(); 

Modifica: Crap. Ho detto che la risposta dovrebbe essere 2 ma intendevo 4. Mi scuso per questo!

Ad esempio: Immagina di essere responsabile della distribuzione degli ID di processo. Si desidera ottenere l'elenco degli ID di processo correnti e emetterne uno successivo, ma il prossimo non dovrebbe essere solo il valore più alto più uno. Piuttosto, dovrebbe essere il prossimo disponibile da un elenco ordinato di ID di processo. Potresti ottenere il successivo disponibile iniziando dal più alto, non ha molta importanza.

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; 
    } 
} 

Usage:

var nextAvailable = myInts.SomeCoolLinqMethod(); 

Answer 2

Ok, ecco la soluzione che mi si avvicinò con che funziona per me.

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

Se qualcuno ha una soluzione più elegante, sarei felice di accettarlo. Ma per ora, questo è quello che sto inserendo nel mio codice e andando avanti.

Modifica: questo è ciò che ho implementato dopo il suggerimento di Kevin di aggiungere un metodo di estensione. E questa era la vera risposta - che nessuna estensione LINQ farebbe in modo che abbia più senso aggiungere il mio. Questo è davvero quello che stavo cercando.

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

Questo sarà abbastanza efficiente:

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 risposta fornita da @ Kevin ha un profilo prestazione indesiderabile. La logica accederà alla sequenza sorgente numerose volte: una volta per la chiamata .Count, una volta per la chiamata .FirstOrDefault e una volta per ciascuna chiamata .Contains. Se l'istanza IEnumerable<int> è una sequenza rinviata, ad esempio il risultato di una chiamata .Select, ciò causerà almeno 2 calcoli della sequenza, insieme a una volta per ogni numero. Anche se si passa un elenco al metodo, esso potrà potenzialmente passare attraverso l'intero elenco per ogni numero selezionato. Immagina di eseguirlo nella sequenza { 1, 1000000 } e puoi vedere come non andrebbe bene.

LINQ tenta di ripetere le sequenze di origine non più di una volta. Questo è possibile in generale e può avere un grande impatto sulle prestazioni del tuo codice. Di seguito è riportato un metodo di estensione che consente di ripetere la sequenza esattamente una volta. Lo fa cercando la differenza tra ciascuna coppia successiva, poi aggiunge 1 al primo numero inferiore che è più di 1 dal numero successivo:

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; 
} 

Poiché questo metodo di estensione può essere chiamato su qualsiasi sequenza arbitraria di interi, ci assicuriamo di ordinarli prima di iterare. Quindi calcoliamo la differenza tra il numero corrente e il numero precedente.Se questo è il primo numero nell'elenco, priorNumber sarà nullo e quindi difference sarà nullo. Se questo non è il primo numero nell'elenco, controlliamo se la differenza rispetto al numero precedente è esattamente 1. In caso contrario, sappiamo che c'è un divario e possiamo aggiungere 1 al numero precedente.

È possibile regolare l'istruzione di reso per gestire le sequenze con 0 o 1 elementi come si ritiene opportuno; Ho scelto di restituire null per le sequenze vuote e n + 1 per la sequenza { n }.

Answer 5

Vedo un sacco di risposte che scrivono un metodo di estensione personalizzato, ma è possibile risolvere questo problema con i metodi di estensione LINQ standard e la statica Enumerable classe:

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

Non so se questo si qualifica come un metodo fresco Linq, ma usando il join esterno sinistro idea da 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(); 

Questo mette l'elaborazione sul lato server SQL se si sta utilizzando LINQ to SQL, e ti permette di non dover tirare le liste d'identità dal server al memo ry.