Wie finde ich ein fortlaufendes Segmentpaar in einer gegebenen Liste von ganzen Zahlen (funktional nicht imperativ)?

Question

Ich habe Liste von ganzen Zahlen wie {1,2,3,5,8,9,10}, ich brauche das folgende Ergebnis [1,3], [5,5], [8,10]

Ich habe die Lösung im imperativen Stil geschrieben, aber ich möchte eine Lösung, die mit der funktionalen Programmierung übereinstimmt.

Meine Imperativ Lösung:

public static List<ContinuousNotificationSegment> ConvertToNotificationSegment(this List<NotificationDTO> input) 
    { 
     var sortedNotificationList = input.Select(n => n.ID).ToList(); 
     sortedNotificationList = sortedNotificationList.OrderBy(n => n).ToList(); 
     List<ContinuousNotificationSegment> continuousSegments = new List<ContinuousNotificationSegment>(); 

     long continuousSegmentStart = 0, continuousSegmentEnd = 0; 

     for (int i = 0; i < sortedNotificationList.Count; i++) 
     {     
      if (IsContinuous(sortedNotificationList[i], ((i + 1) < sortedNotificationList.Count ? sortedNotificationList[i + 1] : -999))) 
      { 
       continuousSegmentStart = continuousSegmentStart == 0 ? sortedNotificationList[i] : continuousSegmentStart; 
      } 
      else 
      { 
       continuousSegmentEnd = sortedNotificationList[i]; 

       continuousSegments.Add(new ContinuousNotificationSegment 
       { 
        MinNotificationId = continuousSegmentStart == 0 ? continuousSegmentEnd : continuousSegmentStart, 
        MaxNotificationId = continuousSegmentEnd 
       }); 

       continuousSegmentStart = 0; 
      } 
     } 

     return continuousSegments; 
    } 

    private static bool IsContinuous(long prevValue, long nextValue) 
    { 
     return nextValue - prevValue == 1; 
    } 

Answer 1

var input = new[] { 1, 2, 3, 5, 8, 9, 10 }; 

var result = 
    input 
     .Skip(1) 
     .Aggregate(
      input.Take(1).Select(x => new { start = x, end = x }).ToList(), 
      (a, x) => 
      { 
       var last = a.Last(); 
       if (last.end + 1 == x) 
       { 
        a[a.Count - 1] = new { start = last.start, end = x }; 
       } 
       else 
       { 
        a.Add(new { start = x, end = x }); 
       } 
       return a; 
      }); 

, das funktioniert. Ich bekomme:

Answer 2

Sie können das tun, indem man zuerst die Liste der Nummern der Bestellung, dann die Nummer wählen und eine Gruppierung-ID, die, wenn die Differenz zwischen der aktuellen Anzahl und dem vorherigen größer als 1 erhöht wird. Dann gruppiere einfach diese Gruppierungs-ID und nimm die Min- und Max-Zahlen als Bereich.

public static IEnumerable<Tuple<int, int>> Runs(this IEnumerable<int> nums) 
{ 
    int? prev = null; 
    int group = 0; 
    return nums.OrderBy(n => n) 
     .Select(
      n => 
      { 
       if (prev.HasValue && n - prev.Value > 1) { group++; } 
       prev = n; 
       return new { group, num = n }; 
      }) 
     .GroupBy(x => x.group) 
     .Select(g => new Tuple<int, int>(g.Min(x => x.num), g.Max(x => x.num))); 
} 

und dieser Code

var nums = new[] { 1, 2, 3, 5, 7, 8, 9 }; 
Console.WriteLine(string.Join(";", nums.Runs())); 

Ausgänge

(1, 3), (5, 5), (7, 9)

Answer 3

die kompakteste und klar LINQ, das ich mir vorstellen konnte, ist dies:

var intList = new List<int> { 1, 2, 3, 5, 8, 9, 10 }; 

var agg = intList.Aggregate(new List<List<int>> { new List<int>() }, (i, j) => 
    { 
     if (!i.Last().Any() || i.Last().Last() + 1 == j) 
      i.Last().Add(j); 
     else 
      i.Add(new List<int> { j }); 
     return i; 
    }).Select(i => new List<int> { i.First(), i.Last() }); 

Das Ergebnis ist genau so, wie in der Frage beschrieben.

Answer 4

Wie ich habe ihn zu programmieren teached funktionell sollte wie folgt aussehen (Achtung, es ist [Pseudo-Code]! Und [Endrekursion]!)

GetRanges(input) 
    if (input == null || input.Count == 0) 
     return {}; 

    var ranges = {}; 
    GetRangesInternal(ranges, {null, null}, input); 
    return ranges; 

GetRangesInternal(ranges, {initialElement, lastElement}, input) => 
    var head = input.Take(1); 
    var tail = input.Skip(1); 

    // no first element - prepare new range and move on 
    if (initialElement == null) 
     GetRangesInternal(ranges, {head, head}, tail); 
     return; 

    // range continued - update it and move on 
    if (head == lastElement+1) 
     GetRangesInternal(ranges, {initialElement, head}, tail) 
     return; 

    // range stopped - add it to result 
    ranges.Add({initialElement, lastElement}); 
    GetRangesInternal(ranges, {head, head}, tail); 

GetRanges ist Einstiegspunkt