How can I check that a sequence of indices of type int are contiguous?

Question

I have a Column class which has an Index property of type int.

If I have a collection of Column objects, I am looking for a way to test if their indices are contiguous. By contiguous I mean that the indices are next to each other, so if ordered by value they are 1 apart from the next and previous Index.

There can be any number of column objects.

So, for example:

• 10,11,12,13 => true

• 3,5,7 => false

• 1,2,4 => false

Edit

While these examples are of ordered indices, I would like a solution that takes an unordered set of indices.

I feel sure there is probably a neat Linq way of solving this, but I cannot see it.

Expressed in code:

public class Column 
{
    public int Index { get; set; }
}

class Program
{
    static void Main(string[] args)
    {
        // Example set of columns 1
        List<Column> columns1 = new List<Column>()
        {
            new Column(){Index = 10},
            new Column(){Index = 11},
            new Column(){Index = 12},
            new Column(){Index = 13},
        };

        // Example set of columns 2
        List<Column> columns2 = new List<Column>()
        {
            new Column(){Index = 3},
            new Column(){Index = 5},
            new Column(){Index = 7},
        };

        // Example set of columns 3
        List<Column> columns3 = new List<Column>()
        {
            new Column(){Index = 1},
            new Column(){Index = 2},
            new Column(){Index = 4},
        };

        var result1 = IndicesAreContiguos(columns1); // => true
        var result2 = IndicesAreContiguos(columns2); // => false
        var result3 = IndicesAreContiguos(columns3); // => false
    }

    public bool IndicesAreContiguos(IEnumerable<Column> columns) 
    {
        // ....???
    }

}

Answer 1

Give this a go:

public static bool IndicesAreContiguos(IEnumerable<Column> columns)
{
    var ordered = columns.Select(x => x.Index).OrderBy(x => x).ToArray();
    return ordered.Skip(1).Zip(ordered, (x, y) => x - y).All(z => z == 1);
}

This is literally "ordered by value they are 1 apart from the next and previous Index."

Answer 2

You don't need LINQ for this

public bool IsContig(int[] arr) {
  for(int i = 1; i<arr.Length;i++)
    if(arr[i] - arr[i-1] != 1)
      return false;
  return true;
}

LINQ is a hammer, but not every problem is a nail

(Edit: to accept an unordered set of indices, then consider a modification that sorts the array first. Again, LINQ isn't necessary; Array.Sort would work)

If a sequence of 1,2,3,2,3,2,3,4,3,2,3,4,5,4,5 is contiguous, improve the IF to allow for a result of -1 too

Answer 3

With math you can create a function which will handle unordered collections with only one iteration over collection.

public static bool IsConsecutive(this IEnumerable<int> values)
{
    return values
        .Aggregate((Sum: 0, Min: int.MaxValue, Max: int.MinValue, Count: 0), 
            (total, value) =>
            {
                total.Count += 1;
                total.Sum += value;
                total.Min = total.Min > value ? value : total.Min;
                total.Max = total.Max < value ? value : total.Max;

                return total;
            },
            (total) =>
            {
                var difference = total.Max - total.Min + 1;
                var expectedSum = (total.Count * (total.Min + total.Max)) / 2;

                return difference == total.Count && expectedSum == total.Sum;
            });
}

Solution is based on the formula of sum of consecutive integers (Gauss's Formula)

But because formula can be applied for consecutive integers with step other than 1 (for example 2, 4, 6, 8), we added check that step is only one by calculating difference between min and max values and comparing it with the quantity of values.

Usage

var values = new[] { 10, 12, 13, 15, 14, 11 };

if (values.IsConsecutive())
{
    // Do something
}

Answer 4

One way would be to create a range from min to max and compare that to the existing indices:

public static bool IndicesAreContiguos(IEnumerable<Column> columns)
{
    var orderedIndices = columns.Select(c => c.Index).OrderBy(i => i);
    if (orderedIndices.Distinct().Count() != columns.Count()) return false;  // Optional.

    int min = columns.Min(c => c.Index);
    int max = columns.Max(c => c.Index);

    return Enumerable.Range(min, max - min + 1).SequenceEqual(orderedIndices);
}