CODEWITHSUNDEEP
c#linqpartitioningstl-algorithm
Matt Kline
Matt Kline

Reputation: 10497

LINQ equivalent of std::partition

What is a LINQ-based function that places all items which satisfy a predicate at the front of the sequence, like C++'s std::partition?

Upvotes: 1

Views: 450

Answers (3)

p.s.w.g
p.s.w.g

Reputation: 149030

If I understand what you're trying to achieve, a simpler solution would be OrderByDescending:

IEnumerable<T> Partition<T>(IEnumerable<T> s, Func<T, bool> predicate)
{
    return s.OrderByDescending(predicate);
}

This works because bool implements IComparable<bool> with false coming before true. So items for which predicate evaluates to true will be placed first in the result set.

And here's a hand-made implementation, just in case you're interested. I haven't done any benchmarks but this one might actually be faster.1

IEnumerable<T> Partition<T>(IEnumerable<T> s, Func<T, bool> predicate)
{
    List<T> falses = new List<T>();
    foreach(var t in s) 
    {
        if (predicate(t)) 
        {
            yield return t;
        }
        else
        {
            falses.Add(t);
        }
    }

    foreach (var t in falses)
    {
        yield return t;
    }
}

1: The hand-made solution is O(n), but OrderBy is considered to be O(n log n). However, depending on the implementation details of the OrderBy method, they might perform nearly identically.

Upvotes: 4

Lumen
Lumen

Reputation: 3574

Using SelectMany, you can improve your own answer:

IEnumerable<T> Partition<T>(IEnumerable<T> s, Func<T, bool> predicate)
{
    return s.GroupBy(predicate).SelectMany(xs => xs);
}

Upvotes: 0

Matt Kline
Matt Kline

Reputation: 10497

My best shot:

IEnumerable<T> Partition<T>(IEnumerable<T> s, Func<T, bool> predicate)
{
    var split = s.GroupBy(predicate);
    return split
        .Where(kv => kv.Key)
        .Single()
        .Concat(split
            .Where(kv => !kv.Key)
            .Single());
}

Upvotes: 0

Related Questions