Detecting sequence of at least 3 sequential numbers from a given list

Question

I have a list of numbers e.g. 21,4,7,9,12,22,17,8,2,20,23

I want to be able to pick out sequences of sequential numbers (minimum 3 items in length), so from the example above it would be 7,8,9 and 20,21,22,23.

I have played around with a few ugly sprawling functions but I am wondering if there is a neat LINQ-ish way to do it.

Any suggestions?

UPDATE:

Many thanks for all the responses, much appriciated. Im am currently having a play with them all to see which would best integrate into our project.

Answer 1

Jon Skeet's / Timwi's solutions are the way to go.

For fun, here's a LINQ query that does the job (very inefficiently):

var sequences = input.Distinct()
                     .GroupBy(num => Enumerable.Range(num, int.MaxValue - num + 1)
                                               .TakeWhile(input.Contains)
                                               .Last())  //use the last member of the consecutive sequence as the key
                     .Where(seq => seq.Count() >= 3)
                     .Select(seq => seq.OrderBy(num => num)); // not necessary unless ordering is desirable inside each sequence.

The query's performance can be improved slightly by loading the input into a HashSet (to improve Contains), but that will still not produce a solution that is anywhere close to efficient.

The only bug I am aware of is the possibility of an arithmetic overflow if the sequence contains negative numbers of large magnitude (we cannot represent the count parameter for Range). This would be easy to fix with a custom static IEnumerable<int> To(this int start, int end) extension-method. If anyone can think of any other simple technique of dodging the overflow, please let me know.

EDIT: Here's a slightly more verbose (but equally inefficient) variant without the overflow issue.

var sequences = input.GroupBy(num => input.Where(candidate => candidate >= num)
                                          .OrderBy(candidate => candidate)
                                          .TakeWhile((candidate, index) => candidate == num + index)
                                          .Last())
                     .Where(seq => seq.Count() >= 3)
                     .Select(seq => seq.OrderBy(num => num));