OmegaMan's Musings

I recently had a need to determine if a sequence of integers was solid, not broken, and whether it contained a gap of any missing numbers to report to the end user. I researched the issue and was dismayed that the examples found on the internet seemed to have unnecessary overheads of copied arrays or other artifacts and were too cumbersome for my needs. From that I wrote these C# extensions which work for any .Net above 3.5. Below I document the extension methods to get the missing numbers of a sequence, quickly determine if a sequence is broken and finally report where the existing numbers before the break of the sequence. See the end for the whole extension class for easier copying.

Problem Definition

If one has a set of numbers say

{ 2, 4, 7, 9 }

it has a broken sequence because there are missing numbers from the set 2-9. Those missing numbers are:

{ 3, 5, 6, 8 }

Find Missing Numbers In a Sequence

This method is the one I created first. It uses the Linq Aggregate extension to enumerate over the numbers in the set. If there is a gap which is greater than 1 between the numbers (the difference below is > 0 but same concept) then it reports the numbers missing between the two.

public static IEnumerable<int> SequenceFindMissings(this IList<int> sequence)
{

    var missing = new List<int>();

    if ((sequence != null) && (sequence.Any()))
    {
        sequence.Aggregate((seed, aggr) =>
                            {
                                var diff = (aggr - seed) - 1;

                                if (diff > 0)
                                    missing.AddRange(Enumerable.Range((aggr - diff), diff));

                                return aggr;
                            });
    }

    return missing;
}

Quickly Determine Broken Sequence

Is the sequence broken from the first number to the last in the set?

public static bool IsSequenceBroken(this IEnumerable<int> sequence)
{
    bool broken = false;

    if (sequence != null) 
    {
        var sequenceAsList = sequence.ToList();

        if (sequenceAsList.Any())
        {
            int lastValue = sequence.First();

            broken = sequence.Any(value =>
                                    {
                                        if ((value - lastValue) > 1)
                                            return true;

                                        lastValue = value;

                                        return false;
                                    }); 
        }
    }

    return broken;
}

Report Last Valid Number Before The Break

This is useful in situations where one needs to report where the break happens, say the user is editing in a grid and one highlights the existing number which precedes the missing number(s).

Example here returns a 2 and 5 which are the numbers which precede the break.

   (new List() { 1, 2, 4, 5, 7, 8}).SequenceReportMissingsBreakStarts()

Here is the method:

public static IEnumerable<int> SequenceReportMissingsBreakStarts(this IList<int> sequence)
{

    var breaks = new List<int>();

    if ((sequence != null) && (sequence.Any()))
    {

        sequence.Aggregate((seed, aggr) =>
                            {
                                var diff = (aggr - seed) - 1;

                                if (diff > 0)
                                    breaks.Add(seed);
                                return aggr;
                            });
    }

    return breaks;
}

Full Extension Source With Comments

Here is the code for an easier copy

public static class SequenceExtensions
{
    /// <summary>
    /// Take a sequence of numbers and if there are any gaps greater than 1 between the numbers,
    /// report true.
    /// </summary>
    /// <param name="sequence">A set of numbers to check.</param>
    /// <returns>True if the there is a break in the sequence of numbers.</returns>
    public static bool IsSequenceBroken(this IEnumerable<int> sequence)
    {
        bool broken = false;

        if (sequence != null)
        {
            var sequenceAsList = sequence.ToList();

            if (sequenceAsList.Any())
            {
                int lastValue = sequence.First();

                broken = sequence.Any(value =>
                                        {
                                            if ((value - lastValue) > 1)
                                                return true;

                                            lastValue = value;

                                            return false;
                                        });
            }
        }

        return broken;
    }

    /// <summary>
    /// Take a sequence of numbers and report the missing numbers. Stop at first break found.
    /// </summary>
    /// <param name="sequence">Set of Numbers</param>
    /// <returns>True of sequence has missing numbers</returns>
    public static IEnumerable<int> SequenceFindMissings(this IList<int> sequence)
    {

        var missing = new List<int>();

        if ((sequence != null) && (sequence.Any()))
        {
            sequence.Aggregate((seed, aggr) =>
                                {
                                    var diff = (aggr - seed) - 1;

                                    if (diff > 0)
                                        missing.AddRange(Enumerable.Range((aggr - diff), diff));

                                    return aggr;
                                });
        }

        return missing;

    }

    /// <summary>
    /// A missing break start in a sequence is where the drop off occurs in the sequence.
    /// For example 3, 5, has a missing break start of the #3 for #4 is the missing.
    /// </summary>
    /// <param name="sequence">Set of Numbers</param>
    /// <returns>The list of break numbers which exist before the missing numbers.</returns>
    public static IEnumerable<int> SequenceReportMissingsBreakStarts(this IList<int> sequence)
    {

        var breaks = new List<int>();

        if ((sequence != null) && (sequence.Any()))
        {

            sequence.Aggregate((seed, aggr) =>
                                {
                                    var diff = (aggr - seed) - 1;

                                    if (diff > 0)
                                        breaks.Add(seed);
                                    return aggr;
                                });
        }

        return breaks;

    }
}

Hope this helps!

Sometimes in C# .Net (see Notes section on usage for before .Net 4)  one might have a list of items and want to make them into pairs. Possibly to take those pairs and place the them into a dictionary. If the items are in a list, that list is linear by nature and using linq is not an option when using the extension ToDictionary.

I have created extension methods to create paired values from any list and those methods are named AsPairs and AsPairsSafe. If the list is odd in length, the final number will be combined with the system default for that type as handled in the method AsPairs. If that is not desired then call AsPairsSafe which will skip the last odd value.

Here is the usage of the AsPairs extension on integers and strings:

var ints = new List<int> { 1, 2, 3, 4, 5 };

IEnumerable<Tuple<int,int>> asTuplePairs = ints.AsPairs();

/* asTuplePairs looks like this(Note value 5 is paired with a default value of 0)
1,2 
3,4
5,0
*/

var strings = new List<string> { "Alpha", "Beta", "Gamma", "Delta", "Omega" };

IEnumerable<Tuple<string,string>> asTuplePairsStrings = strings.AsPairs();

/* asTuplePairsStrings (note Omega is paired a default value of Null)
Alpha, Beta 
Gamma, Delta
Omega, NULL

Whereas the call to AsPairsSafe would return without Omega:
Alpha, Beta 
Gamma, Delta
*/

Here are the extension methods:

public static class MyExtensions
{
   // Create Pairs from a list. If the list is odd add a default value for the final pair. 
   public static IEnumerable<Tuple<T, T>> AsPairs<T>(this List<T> list)
   {
      int index = 0;

      while (index < list.Count())
      {
         if (index + 1 > list.Count())
            yield break;

         if (index + 1 == list.Count())    
            yield return new Tuple<T,T>(list[index++],  default(T));
         else
            yield return new Tuple<T,T>(list[index++],  list[index++]);
      }
   }

   // Create Pairs from a list. Note if the list is not even in count, the last value is skipped.
   public static IEnumerable<Tuple<T, T>> AsPairsSafe<T>(this List<T> list)
   {
      int index = 0;

      while (index < list.Count())
      {
         if (index + 1 >= list.Count())
            yield break;

         yield return new Tuple<T,T>(list[index++],  list[index++]);
      }

   }
}

Notes

Tuple is a .Net 4 item. If you are using a previous version of .Net use the KeyValuePair structure instead.

Finding Identical Strings using GroupBy

List<string> theList = new List<string>() { "Alpha", "Alpha", "Beta", "Gamma", "Delta" };

theList.GroupBy(txt => txt)
        .Where(grouping => grouping.Count() > 1)
        .ToList()
        .ForEach(groupItem => Console.WriteLine("{0} duplicated {1} times with these values {2}",
                                                 groupItem.Key, 
                                                 groupItem.Count(),
                                                 string.Join(" ", groupItem.ToArray())));
// Writes this out to the console:
//
// Alpha duplicated 2 times with these values Alpha Alpha

Line By Line Explanation

GroupBy Usage with Only Two Defined Keys Regex Example

List<string> theList = new List<string>() { "Alpha", "Alpha", "Beta", "Gamma", "Delta" };

theList.GroupBy( txt => Regex.IsMatch( txt, "ta$" ))
       .ToList()
       .ForEach(groupItem => Console.WriteLine("{0} found {1} times with these values: {2}",
                                                 groupItem.Key,
                                                 groupItem.Count(),
                                                 string.Join(" ", groupItem.ToArray())));
// Output
// False found 3 times with these values: Alpha Alpha Gamma
// True found 2 times with these values: Beta Delta

GroupBy Usage with one Key or a Non Related Key

List<string> theList = new List<string>() { "Alpha", "Alpha", "Beta", "Gamma", "Delta" };

theList.GroupBy(txt => 1 )
        .ToList()
        .ForEach(groupItem => Console.WriteLine("The Key ({0}) found a total of {1} times with a total letter count of {2} characters",
                                                 groupItem.Key,
                                                 groupItem.Count(),
                                                 groupItem.Sum(it => it.Count())));

// Output:
// The Key (1) found a total of 5 times with a total letter count of 24 characters