How to use LINQ to search for 5 elements in a row that match a single predicate, but where there is no sixth element?

Question

I am trying to learn LINQ, and it seems that searching for a series of "n" elements matching the predicate should be possible, but I cannot figure out how to approach the problem.

My solution actually needs a second, different predicate to check the "end" of the sequence, but finding the first element that failed the test, after a sequence of at least 5 elements that pass the test, will also be interesting.

Here is my naive non-LINQ approach ....

int numPassed = 0; for (int i = 0; i < array.Count - 1; i++ ) { if (FirstTest(array[i])) { numPassed++; } else { numPassed = 0; } if ((numPassed > 5) && SecondTest(array[i + 1])) { foundindex = i; break; } } 

Answer 1

A real LINQ solution is possible, but frankly pretty ugly. The idea is to isolate subsequences that match the description (a series of N elements matching the predicate that ends when the element is found matching the second predicate), and then select the first one with the shortest length.

Let's say the parameters are:

 var data = new[] { 0, 1, 1, 1, 0, 0, 2, 2, 2, 2, 2 }; Func<int, bool> acceptPredicate = i => i != 0; // The reverse of acceptPredicate, but could be otherwise Func<int, bool> rejectPredicate = i => i == 0; 

Isolating subsequences are possible with GroupBy and a bunch of ugly GroupBy code (there is an inherent awkwardness here - you need to maintain a non-trivial state). The idea is to group with an artificial and arbitrary “group number”, choosing a different number whenever we move from a subsequence that can be acceptable to one that is definitely unacceptable and when the opposite happens:

 var acceptMode = false; var groupCount = 0; var groups = data.GroupBy(i => { if (acceptMode && rejectPredicate(i)) { acceptMode = false; ++groupCount; } else if (!acceptMode && acceptPredicate(i)) { acceptMode = true; ++groupCount; } return groupCount; }); 

The last step (finding the first group of acceptable length) is simple, but there is one last mistake: make sure that you do not select one of the groups that do not satisfy the specified condition:

 var result = groups.Where(g => !rejectPredicate(g.First())) .FirstOrDefault(g => g.Count() >= 5); 

All of the above is achieved in one pass along the original sequence.

Please note that this code will take a sequence of elements that also ends the original sequence (i.e. it does not end because we found an element that satisfies rejectPredicate , but because we ran out of data). If you do not want this, a small modification is required.

Look at the action .

Answer 2

Not elegant, but this will work:

 var indexList = array .Select((x, i) => new { Item = x, Index = i }) .Where(item => item.Index + 5 < array.Length && FirstTest(array[item.Index]) && FirstTest(array[item.Index+1]) && FirstTest(array[item.Index+2]) && FirstTest(array[item.Index+3]) && FirstTest(array[item.Index+4]) && SecondTest(array[item.Index+5])) .Select(item => item.Index); 

Answer 3

Instead of trying to combine existing extension methods, it is much easier to use Enumerator .

---

Example:

 IEnumerable<T> MatchThis<T>(IEnumerable<T> source, Func<T, bool> first_predicate, Int32 times_match, Func<T, bool> second_predicate) { var found = new List<T>(); using (var en = source.GetEnumerator()) { while(en.MoveNext() && found.Count < times_match) if (first_predicate((T)en.Current)) found.Add((T)en.Current); else found.Clear(); if (found.Count < times_match && !en.MoveNext() || !second_predicate((T)en.Current)) return Enumerable.Empty<T>(); found.Add((T)en.Current); return found; } } 

Application:

 var valid_seq = new Int32[] {800, 3423, 423423, 1, 2, 3, 4, 5, 200, 433, 32}; var result = MatchThis(valid_seq, e => e<100, 5, e => e>100); 

Result:

Answer 4

It looks like you want 6 continuous elements, the first 5 of which correspond to predicate1, and the last (sixth) corresponds to predicate2. Your version without linq works fine, using linq is a little reluctant in this case. And trying to solve the problem in a single linq query makes the problem more complicated, here is a (possibly) cleaner linq solution:

 int continuous = 5; var temp = array.Select(n => FirstTest(n) ? 1 : 0); var result = array.Where((n, index) => index >= continuous && SecondTest(n) && temp.Skip(index - continuous).Take(continuous).Sum() == continuous) .FirstOrDefault(); 

Everything will be easier if you are Morelinq.Batch .

Answer 5

 var result = array.GetSixth(FirstTest).FirstOrDefault(SecondTest); internal static class MyExtensions { internal static IEnumerable<T> GetSixth<T>(this IEnumerable<T> source, Func<T, bool> predicate) { var counter=0; foreach (var item in source) { if (counter==5) yield return item; counter = predicate(item) ? counter + 1 : 0; } } } 

Answer 6

Like others, LINQ is not an ideal solution for this pattern matching. But still, it is possible, and it should not be ugly:

 Func<int, bool> isBody = n => n == 8; Func<int, bool> isEnd = n => n == 2; var requiredBodyLength = 5; // Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 int[] sequence = { 6, 8, 8, 9, 2, 1, 8, 8, 8, 8, 8, 8, 8, 2, 5 }; // ^-----------^ ^ // Body End // First we stick an index on each element, since that the desired output. var indexedSequence = sequence.Select((n, i) => new { Index = i, Number = n }).ToArray(); // Scroll to the right to see comments var patternMatchIndexes = indexedSequence .Select(x => indexedSequence.Skip(x.Index).TakeWhile(x2 => isBody(x2.Number))) // Skip all the elements we already processed and try to match the body .Where(body => body.Count() == requiredBodyLength) // Filter out any body sequences of incorrect length .Select(body => new { BodyIndex = body.First().Index, EndIndex = body.Last().Index + 1 }) // Prepare the index of the first body element and the index of the end element .Where(x => x.EndIndex < sequence.Length && isEnd(sequence[x.EndIndex])) // Make sure there is at least one element after the body and that it an end element .Select(x => x.BodyIndex) // There may be more than one matching pattern, get all their indices .ToArray(); //patternMatchIndexes.Dump(); // Uncomment in LINQPad to see results 

Please note that this implementation does not work at all, it is intended only for training, to show how something can be done in LINQ, despite the unsuitability of its solution in this way .