Detecting consecutive integers and collapse to string

Question

_{Disclaimer: A very similar question was already asked in a Python context here. This is about C#.}

I have an enumeration containing integers such as:

[1, 2, 3, 4, 7, 8, 10, 11, 12, 13, 14]

I'd like to obtain a string putting out the ranges of consecutive integers:

1-4, 7-8, 10-14

I came up with:

public static void Main()
{
    System.Diagnostics.Debug.WriteLine(FindConsecutiveNumbers(new int[] { 1,2, 7,8,9, 12, 15, 20,21 }));
}

private static string FindConsecutiveNumbers(IEnumerable<int> numbers)
{
    var sb = new StringBuilder();
    int? start = null;
    int? lastNumber = null;
    const string s = ", ";
    const string c = "-";

    var numbersPlusIntMax = numbers.ToList();
    numbersPlusIntMax.Add(int.MaxValue);
    foreach (var number in numbersPlusIntMax)
    {
        var isConsecutive = lastNumber != null && lastNumber + 1 == number;
        if (!isConsecutive)
        {
            if (start != null)
            {
                if (sb.Length > 0) { sb.Append(s); }
                if (start == lastNumber)
                {
                    sb.Append(start); ;
                }
                else
                {
                    sb.Append(start + c + lastNumber); ;
                }
            }

            start = number;
        }
                
        lastNumber = number;
    }

    return sb.ToString();
}

This algorithm works for ordered input. Is there a built-in/LINQ/shorter C# way of doing this?

score 6 · Accepted Answer · answered Aug 26 '20 at 09:06

6

int[] numbers = { 1, 2, 3, 4, 7, 8, 10, 11, 12, 13, 14 };

return string.Join(", ",
    numbers
        .Select((n, i) => new { value = n, group = n - i })
        .GroupBy(o => o.group)
        .Select(g => g.First().value + "-" + g.Last().value)
);

answered Aug 26 '20 at 09:06

shingo

18,436
5
23
42

1

`.Select(g => g.First().value == g.Last().value ? $"{g.First().value}" : $"{g.First().value}-{g.Last().value}")` in order to stick to required format – Dmitry Bychenko Aug 26 '20 at 09:29

Dmitry Bychenko · Answer 2 · 2020-08-26T08:34:09.930

I suggest decomposition: Let's split initial routine into logics:

private static IEnumerable<(int left, int right)> Consecutive(IEnumerable<int> numbers) {
  int start = -1;
  int stop = -2;  

  foreach (var item in numbers) // numbers.OrderBy(x => x) to sort numbers
    if (item == stop + 1)
      stop = item;
    else {
      if (stop >= start)
        yield return (start, stop);

      start = item;
      stop = item;
    }  

  if (stop >= start)
    yield return (start, stop);  
}

and representation

private static string FindConsecutiveNumbers(IEnumerable<int> numbers) =>
  string.Join(", ", Consecutive(numbers)
    .Select(item => item.left == item.right 
       ? $"{item.left}" 
       : $"{item.left}-{item.right}"));

Then business as usual:

public static void Main()
{
    // 1-2, 7-9, 12, 15, 20-21
    System.Diagnostics.Debug.WriteLine(FindConsecutiveNumbers(new int[] { 
      1, 2, 
      7, 8, 9, 
      12, 
      15, 
      20, 21 }
    ));
}

Nice usage of [Tuple types](https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/builtin-types/value-tuples)! — Jack Miller, Aug 26 '20 at 09:48

score 0 · Answer 3 · answered Aug 26 '20 at 23:14

0

If we could get the numbers in a List instead of an enumeration then we do not need to access all the numbers. The previous answers are have a time complexity of O(n) where n is the size of the array. Whereas if we have a list, this problem could be solved in O(klogn) where k is the number of groups.

Basically you could use a slightly modified binary search to find the end point of a group which could be done in O(logn) And then from end+1, you could do the same for the next group.

answered Aug 26 '20 at 23:14

Nuri Tasdemir

9,720
3
42
67

1

A binary search. Also a nice idea. But if I understood the approach correctly, this will only prove advantages if there are few groups. – Jack Miller Aug 27 '20 at 09:04
That's right. If it is expected that every group will have very few elements (which means there are lots of groups) than there is no point using this approach. – Nuri Tasdemir Aug 27 '20 at 21:07
@JackMiller, we could also modify the binary search in a way that at the worst case it will be O(n) instead of O(nlogn) in the case of k = n. Therefore the complexity will be the better of O(klogn) and O(n). – Nuri Tasdemir Sep 28 '20 at 22:55

Detecting consecutive integers and collapse to string

3 Answers3