32

Is there a quick and nice way using linq?

nawfal
  • 70,104
  • 56
  • 326
  • 368
  • @AakashM, Its almost sure that by lambda expressions OP meant linq, and not some delegate/expression approach. No idea why the edit was reverted. – nawfal May 30 '13 at 08:55
  • @nawfal 1) there's no way to suspect what this unregistered user meant 4+years ago, even less to be 'almost sure'. 2) [tag:find-occurrences] is a poor and in any case inappropriate tag. 3) The word "linq" isn't code and so shouldn't be formatted as code. Three at-best-questionable parts to an edit to my mind make perfectly good grounds for reversion, but feel free to take it to meta if you disagree. – AakashM May 30 '13 at 09:09
  • @AakashM I agree with 3. Nevertheless the gist of my edit was a more sensible question. You could have removed the inappropriate (?) tag, and also the code formatting if that is what mattered by reediting rather than reverting. So now, *in any case inappropriate tag*, so for what type of questions is it more suitable?. 2) what do you think OP must have meant by *lambda expressions*? My point is there **is a way to suspect** having been in C# circle for a while, and its a strong suspicion given the answer OP has chosen. – nawfal May 30 '13 at 09:24

6 Answers6

94

How about:

var most = list.GroupBy(i=>i).OrderByDescending(grp=>grp.Count())
      .Select(grp=>grp.Key).First();

or in query syntax:

var most = (from i in list
            group i by i into grp
            orderby grp.Count() descending
            select grp.Key).First();

Of course, if you will use this repeatedly, you could add an extension method:

public static T MostCommon<T>(this IEnumerable<T> list)
{
    return ... // previous code
}

Then you can use:

var most = list.MostCommon();
Marc Gravell
  • 1,026,079
  • 266
  • 2,566
  • 2,900
  • Thats what I was trying to get at, but my brain just ain't working at the moment. – Nathan W Dec 10 '08 at 13:26
  • 6
    What if more than one element is the answer? – Varun Mahajan Dec 10 '08 at 13:34
  • 2
    Best solution with native LINQ. Although with [MoreLINQ](http://morelinq.googlecode.com/)'s `MaxBy()` you could even do the following: `list.GroupBy(i=>i).MaxBy(g=>g.Count()).Key`. Aside from being shorter and clearer, it should theoretically be more efficient for large data sets (max vs. sort). – Allon Guralnek May 31 '13 at 10:03
  • Thanks Marc. It enabled me to apply most frequent kmers problem without any fuss. – Failed Scientist May 16 '16 at 05:45
5

Not sure about the lambda expressions, but I would

  1. Sort the list [O(n log n)]

  2. Scan the list [O(n)] finding the longest run-length.

  3. Scan it again [O(n)] reporting each number having that run-length.

This is because there could be more than one most-occurring number.

Mike Dunlavey
  • 40,059
  • 14
  • 91
  • 135
3

Taken from my answer here:

public static IEnumerable<T> Mode<T>(this IEnumerable<T> input)
{            
    var dict = input.ToLookup(x => x);
    if (dict.Count == 0)
        return Enumerable.Empty<T>();
    var maxCount = dict.Max(x => x.Count());
    return dict.Where(x => x.Count() == maxCount).Select(x => x.Key);
}

var modes = { }.Mode().ToArray(); //returns { }
var modes = { 1, 2, 3 }.Mode().ToArray(); //returns { 1, 2, 3 }
var modes = { 1, 1, 2, 3 }.Mode().ToArray(); //returns { 1 }
var modes = { 1, 2, 3, 1, 2 }.Mode().ToArray(); //returns { 1, 2 }

I went for a performance test between the above approach and David B's TakeWhile.

source = { }, iterations = 1000000
mine - 300 ms, David's - 930 ms

source = { 1 }, iterations = 1000000
mine - 1070 ms, David's - 1560 ms

source = 100+ ints with 2 duplicates, iterations = 10000
mine - 300 ms, David's - 500 ms

source = 10000 random ints with about 100+ duplicates, iterations = 1000
mine - 1280 ms, David's - 1400 ms

Community
  • 1
  • 1
nawfal
  • 70,104
  • 56
  • 326
  • 368
1

Here is another answer, which seems to be fast. I think Nawfal's answer is generally faster but this might shade it on long sequences.

public static IEnumerable<T> Mode<T>(
    this IEnumerable<T> source,
    IEqualityComparer<T> comparer = null)
{
    var counts = source.GroupBy(t => t, comparer)
        .Select(g => new { g.Key, Count = g.Count() })
        .ToList();

    if (counts.Count == 0)
    {
        return Enumerable.Empty<T>();
    }

    var maxes = new List<int>(5);
    int maxCount = 1;

    for (var i = 0; i < counts.Count; i++)
    {
        if (counts[i].Count < maxCount)
        {
            continue;
        }

        if (counts[i].Count > maxCount)
        {
            maxes.Clear();
            maxCount = counts[i].Count;
        }

        maxes.Add(i);
    }

    return maxes.Select(i => counts[i].Key);
}
Community
  • 1
  • 1
Jodrell
  • 34,946
  • 5
  • 87
  • 124
0

Someone asked for a solution where there's ties. Here's a stab at that:

int indicator = 0

var result =
  list.GroupBy(i => i)
    .Select(g => new {i = g.Key, count = g.Count()}
    .OrderByDescending(x => x.count)
    .TakeWhile(x =>
    {
      if (x.count == indicator || indicator == 0)
      {
        indicator = x.count;
        return true;
      }
      return false;
    })
    .Select(x => x.i);
Amy B
  • 108,202
  • 21
  • 135
  • 185
0

Here's a solution I've written for when there are multiple most common elements.

public static List<T> MostCommonP<T>(this IEnumerable<T> list)
    {
        return list.GroupBy(element => element)
                   .GroupBy(group => group.Count())
                   .MaxBy(groups => groups.Key)
                   .Select(group => group.Key)
                   .ToList();
    }
Foxicution
  • 1
  • 1