Use LINQ to group a sequence of numbers with no gaps

Question

With this array int[]{ 1, 2, 3, 4, 7, 8, 11, 15,16,17,18 }; How can i convert to this string array "1-4","7-8","11","15-18"

Suggestions ? Linq ?

Answer 1

var array = new int[] { 1, 2, 3, 4, 7, 8, 11, 15, 16, 17, 18 };

var result = string.Join(",", array
    .Distinct()
    .OrderBy(x => x)
    .GroupAdjacentBy((x, y) => x + 1 == y)
    .Select(g => new int[] { g.First(), g.Last() }.Distinct())
    .Select(g => string.Join("-", g)));

with

public static class LinqExtensions
{
    public static IEnumerable<IEnumerable<T>> GroupAdjacentBy<T>(
        this IEnumerable<T> source, Func<T, T, bool> predicate)
    {
        using (var e = source.GetEnumerator())
        {
            if (e.MoveNext())
            {
                var list = new List<T> { e.Current };
                var pred = e.Current;
                while (e.MoveNext())
                {
                    if (predicate(pred, e.Current))
                    {
                        list.Add(e.Current);
                    }
                    else
                    {
                        yield return list;
                        list = new List<T> { e.Current };
                    }
                    pred = e.Current;
                }
                yield return list;
            }
        }
    }
}

Answer 2

You don't need Linq; in fact, the easiest solution requires knowing about three positions in the array (your starting number, current number and the next number after the current), for which Enumerables are not well-suited.

Try this:

var start = 0;
var end = 0;
var write = false;
var builder = new StringBuilder();
for(var i=0; i<array.Length; i++)
{
   //arranged this way to avoid ArrayOutOfBoundException
   //if the next index doesn't exist or isn't one greater than the current,
   //the current index is the end of our incremental range.
   if(i+1 == array.Length || array[i+1] > array[i] + 1)
   {
      end = i;
      write = true;
   }

   if(write)
   {
      if(end - start == 0) //one number
         builder.Append(String.Format("{0}, ", array[start]);
      else //multi-number range
         builder.Append(String.Format("{0}-{1}, ", array[start], array[end]);

      start = i+1;
      end = i+1; //not really necessary but avoids any possible case of counting backwards
      write = false;
   }  

}

You can rearrange this to reduce nesting of code, continue early in the loop logic, and remove a few vars; you'll gain a few millis of execution time. You'll also need to trim the last two characters (a trailing comma and space) off the end of the StringBuilder before getting the String out.

Answer 3

Here is a cut at it:

public static IEnumerable<string> ToRanges(this IEnumerable<int> values)
{
    int? start = null, end = null;
    foreach (var value in values.OrderBy(vv => vv))
    {
        if (!start.HasValue)
        {
            start = value;
        }
        else if (value == (end ?? start) + 1)
        {
            end = value;
        }
        else
        {
            yield return end.HasValue
                ? String.Format("{0}-{1}", start, end)
                : String.Format("{0}", start);
            start = value;
            end = null;
        }
    }

    if (start.HasValue)
    {
        yield return end.HasValue
            ? String.Format("{0}-{1}", start, end)
            : String.Format("{0}", start);
    }
}

Answer 4

What's the algorithm you want to implement? Figure out what you want to happen, then see if it could be made clearer with a LINQ translation. Here's something non-LINQ that could give you an idea.

int[] array = { 1, 2, 3, 4, 7, 8, 11, 15, 16, 17, 18};
List<string> ranges = new List<string>();

// code assumes array is not zero-length, is distinct, and is sorted.
// to do: handle scenario as appropriate if assumptions not valid

Action<int, int, List<string>> addToRanges = (first, last, list) =>
{
    if (last == first)
        list.Add(last.ToString());
    else
        list.Add(string.Format("{0}-{1}", first, last)); ;
};

int firstItem = array[0];
int lastItem = firstItem;
foreach (int item in array.Skip(1))
{
    if (item > lastItem + 1)
    {
        addToRanges(firstItem, lastItem, ranges);
        firstItem = lastItem = item;
    }
    else
    {
        lastItem = item;
    }
}

addToRanges(firstItem, lastItem, ranges);

// return ranges or ranges.ToArray()