how to count sequence lengths in linq

Question

I have a list of 1s and 0s. Say: 1,1,1,0,0,1,1,1,1,1,0,1,1,1,0,0,0,1

I want to get the max length of sequences of 1s.

In this case, the sequences are 3,5,3,1 and the max is 5.

I have this code (using answer from an S.O. question: Getting pair set using linq)

var list = new[]{1,1,1,0,0,1,1,1,1,1,0,1,1,1,0,0,0,1}.ToList();
var pairs = list.Where( (e,i) => i < list.Count - 1 )
            .Select( (e,i) => new { A = e, B = list[i+1] }  ).ToList();
var analyzed = pairs.ConvertAll( p=> new ... not sure how to continue

That `Where` seems like a complicated way to do `Take(list.Count-1)`. — NetMage, Sep 18 '17 at 20:54

score 2 · Answer 1 · answered Sep 18 '17 at 14:48

2

I don't recommend linq as well, since it takes more time to get to the solution when you can easily get one.

I am using the index of 0 to locate the length of 1s.

var list = new[]{1,1,1,0,0,1,1,1,1,1,0,1,1,1,0,0,0,1}.ToList();

int previousIndex= -1;
int index = list.IndexOf(0);

int max = index < 0 ? list.Count() : 0;
while(index >=0)
{
    int currentLength = index - previousIndex - 1;
    max = max > currentLength ? max : currentLength;
    previousIndex = index;
    index = list.IndexOf(0, index + 1);

    // if sequence of 1 in the end of array
    if(index < 0)
    {
        currentLength = list.Count() -  previousIndex - 1;
        max = max > currentLength ? max : currentLength;
    }
}

Console.WriteLine(max);

answered Sep 18 '17 at 14:48

Liu

970
7
19

ah, focusing on linq I forgot list's own methods. +1 for `IndexOf` – René Vogt Sep 18 '17 at 17:33
What do you mean by "more time to get to the solution"? – Enigmativity Sep 18 '17 at 22:44
@Enigmativity I mean in this case, it's easier to just go straight forward, I don't see any reason to use linq and it will take your time. – Liu Sep 19 '17 at 07:44
@JianpingLiu - Do you mean that using a `while` loop is simpler and less time consuming to write? – Enigmativity Sep 19 '17 at 07:47
That's a smart way (genius!) of accomplishing this! But I need to do it "straightforward" and with Linq for re-use in something else I'm doing... So I'll upvote this but cannot choose it as the solution. – pashute Sep 19 '17 at 15:43

score 2 · Answer 2 · answered Sep 18 '17 at 15:07

A very nice and reusable solution using the GroupAdjacentBy extension from this answer by dtb:

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;
        }
    }
}

var list = new[] { 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1 }.ToList();
var grouped = list.GroupAdjacentBy((x, y) => x == y); // Group identical adjacent elements together into sublists
int result = grouped.Max(s => s.Count()); // Get longest sublist

This looks like the best answer! Thanks. I'm going over the others and will probably mark it as the answer. [Edit] @Enigmativity does something like this without any helper methods, (and Slai wrote one extremely succinct- but not immediately apparent how it works using the zero with multiplication to stop the continued aggregation) . Still thank you so much!! — pashute, Sep 19 '17 at 15:55

score 2 · Accepted Answer · answered Sep 18 '17 at 22:48

This seems to work quite easily:

var list = new[]{1,1,1,0,0,1,1,1,1,1,0,1,1,1,0,0,0,1}.ToList();

var maxOnes =
    list
        .Aggregate(
            new { Max = 0 , Current = 0 },
            (a, x) => x == 0
                ? new { Max = a.Max , Current = 0 }
                : new { Max = a.Max > a.Current + 1
                    ? a.Max
                    : a.Current + 1 , Current = a.Current + 1 })
        .Max;

It's a single pass through the list so very performant.

Readable, simple, short (although not as short as @Slai 's) – pashute Sep 19 '17 at 15:59 — pashute, Sep 19 '17 at 15:59

score 1 · Answer 4 · answered Sep 18 '17 at 22:19

1

Using an extension method to provide a Split for IEnumerable analogous to String.Split,

public static IEnumerable<IEnumerable<T>> Split<T>(this IEnumerable<T> src, Func<T, bool> atSplit) {
    IEnumerable<T> NextSplit(IEnumerator<T> e) {
        while (!atSplit(e.Current)) {
            yield return e.Current;
            if (!e.MoveNext())
                yield break;
        }
    }

    var srce = src.GetEnumerator();
    while (srce.MoveNext())
        yield return NextSplit(srce);
}

Then your answer is:

var ans = list.Split(n => n == 0).Select(sl => sl.Count()).Max();

answered Sep 18 '17 at 22:19

NetMage

26,163
3
34
55

This too is a smart way to do it. But I'm looking for the Linq way of actually aggragating... and not an algorithm in code. Upvoting your answer and thanks! but this won't be the chosen answer. Sorry – pashute Sep 19 '17 at 15:46
Perhaps your question needs to be clearer? In any case, why do you want to use Linq aggregation? – NetMage Sep 19 '17 at 17:48

score 1 · Answer 5 · answered Sep 18 '17 at 22:58

Not sure why the other answers are being over-complicated with LINQ and iterators and predicates... when a basic foreach loop will suffice to find the maximum consecutive sequence count. Nothing fancy:

public static int GetMaxSequenceCount( IEnumerable<int> items, int match )
{
    int max = 0;
    int total = 0;

    foreach( int i in items )
    {
        if( i == match )
        {
            total++;
            max = total > max ? total : max;
            continue;
        }

        total = 0;
    }

    return max;
}

Because I want to know how to do this in linq. And I know how to do it with regular programming. — pashute, Sep 19 '17 at 15:57

score 1 · Answer 6 · answered Sep 19 '17 at 03:25

1

Few shorter alternatives:

int max1 = string.Concat(list).Split('0').Max().Length;

int max2 = list.Aggregate(new int[2], (a, i) => new[]{Math.Max(a[0], a[1]+i), ++a[1]*i})[0];

int max3 = list.Aggregate(new int[2], (a, i) => { a[1] = ++a[1] * i; a[0] = a.Max(); return a; })[0];

answered Sep 19 '17 at 03:25

Slai

22,144
5
45
53

Would you care to explain the last two? The first is not for me. See my remark to @NetMage on the Linq.Split solution. But, of course, ingenious. upvoting in any case. – pashute Sep 19 '17 at 15:49
@pashute it's pretty much the same as the accepted answer, but it relies on the numbers being only 0 and 1 so doesn't work for other numbers. It starts with 2 `0` variables `new int[2]` for max and currentMax. `a[1] = ++a[1] * i` is short for `currentMax = currentItem == 0 ? 0 : currentMax + 1`, and `a[0] = a.Max()` is short for `max = Math.Max(max, currentMax)` – Slai Sep 19 '17 at 18:38

how to count sequence lengths in linq

6 Answers6