How to get top N elements of a list with LinQ?

Question

I have an ordered list by exam points and I want to have the top N element of this list.
If the N(th) and N+1(th) students have the same exam points, the list must have them both.

For example I have a list like this:

john.   80  
mike.   75  
james.  70  
ashley. 70
kate.   60

Top 3 should return john, mike, james, ashley
I tried Take() but it returns only john, mike, james

English is not my main language, sorry if I couldn't tell correctly
Thanks

@Shaharyar i tried this http://stackoverflow.com/questions/319973/how-to-get-first-n-elements-of-a-list-in-c — AhmetEmre90, Sep 29 '14 at 12:25
What if more than two students have the same marks? Will you take them all? — Shaharyar, Sep 29 '14 at 12:27
possible duplicate of [LINQ to Entities equivalent of sql "TOP(n) WITH TIES"](http://stackoverflow.com/questions/22157211/linq-to-entities-equivalent-of-sql-topn-with-ties) — VoteCoffee, Sep 29 '14 at 12:28
There is no native LINQ support of WITH TIES. There are several ways to do this. See the duplicate question referenced above. — VoteCoffee, Sep 29 '14 at 12:30
@AhmetEmre90: would you please clarify your requirement by editing your question and providing more meaningful sample data? For instance, what if there are two with 80, two with 70 and two with 60, do you want to get six items or do you want to get two 80 + two 70? — Tim Schmelter, Sep 29 '14 at 12:51

score 10 · Answer 1 · answered Sep 29 '14 at 12:34

Here's a one-pass-only implementation:

public static IEnumerable<TSource> TopWithTies<TSource, TValue>(
    this IEnumerable<TSource> source,
    int count,
    Func<TSource, TValue> selector)
{
    if (source == null) throw new ArgumentNullException("source");
    if (selector == null) throw new ArgumentNullException("selector");
    if (count < 0) throw new ArgumentOutOfRangeException("count");
    if (count == 0) yield break;
    using(var iter = source.OrderByDescending(selector).GetEnumerator())
    {
        if(iter.MoveNext())
        {
            yield return iter.Current;
            while (--count >= 0)
            {
                if(!iter.MoveNext()) yield break;
                yield return iter.Current;    
            }
            var lastVal = selector(iter.Current);
            var eq = EqualityComparer<TValue>.Default;
            while(iter.MoveNext() && eq.Equals(lastVal, selector(iter.Current)))
            {
                yield return iter.Current;
            }
        }
    }
}

Example usage:

var data = new[]
{
    new { name = "john", value = 80 },
    new { name = "mike", value = 75 },
    new { name = "james", value = 70 },
    new { name = "ashley", value = 70 },
    new { name = "kate", value = 60 }
};
var top = data.TopWithTies(3, x => x.value).ToList();
foreach(var row in top)
{
    Console.WriteLine("{0}: {1}", row.name, row.value);
}

That's not actually one pass, because `OrderByDescending` itself will do a `n*Log(n)` sort — Charlieface, Jul 05 '22 at 11:39

Tim Schmelter · Answer 2 · 2014-09-29T12:53:11.820

3

What if more than two students have the same marks? Will you take them all? OP: Yes

You can group by the points, then use OrderByDescending + Take + SelectMany:

var topThreePoints = users.GroupBy(u => u.Points)
                          .OrderByDescending(g => g.Key)
                          .Take(3)
                          .SelectMany(g => g);

edited Sep 29 '14 at 12:53

answered Sep 29 '14 at 12:25

Tim Schmelter

450,073
74
686
939

3

That takes the first 3 groups, though - if the 1st group has 200 items, you wouldn't take any from any other groups – Marc Gravell Sep 29 '14 at 12:25
@Marc, I don't understand your comment. If the first group has 200 items and `SelectMany()` projects from the top 3 groups, surely the result will include these 200 items plus the items in the two other groups, right? – Frédéric Hamidi Sep 29 '14 at 12:27
1

@FrédéricHamidi not if the intent is `TOP WITH TIES`, no. – Marc Gravell Sep 29 '14 at 12:27
@MarcGravell: maybe my understanding of the question is incorrect. But i guess OP wants to include all ties. – Tim Schmelter Sep 29 '14 at 12:30
1

For what it's worth, I read the question the same way Tim does. Also note the questioner never acknowledged Marc's comment and may not be looking for a WITH TIES solution after all -- it's not clear. – Frédéric Hamidi Sep 29 '14 at 12:32

score 2 · Answer 3 · answered Sep 29 '14 at 12:29

What you probably want to do is

Get the nth
get all when >= nth

i.e.

var nth = users.Skip(n-1).FirstOrDefault()
var top = users.TakeWhile(user => user.Score >= nth.Score)

(This assumes that the list is ordered descending, as in the example given in the question. Also will throw an error if there are < n elements in the input list)

score 0 · Answer 4 · answered Sep 29 '14 at 12:29

I have created a sample case in LINQPad.

var a = new List<Tuple<string,int>>();
a.Add(new Tuple<string,int>("john",80));
a.Add(new Tuple<string,int>("mike",75));
a.Add(new Tuple<string,int>("james",70));
a.Add(new Tuple<string,int>("ashley",70 ));
a.Add(new Tuple<string,int>("kate",60  ));

a.Where(x=>x.Item2>=a.OrderBy(i=>i.Item2).Skip(2).Take(1).SingleOrDefault ().Item2).Dump();

Don't know if it is efficient enough though.

score 0 · Answer 5 · answered Sep 29 '14 at 12:30

0

Maybe like so?

list.TakeWhile((item, index) => index < N || list[index] == list[index + 1]);

answered Sep 29 '14 at 12:30

Dennis_E

8,751
23
29

1

This looks nice, but it might index `list[list.Length]`. I think `list[index] == list[index - 1]` doesn’t have that problem, because `index < N` holds when `index` is 0. – Lumen Sep 29 '14 at 12:50

How to get top N elements of a list with LinQ?

5 Answers5