Group objects by equality

Question

I have a collection of objects which I would like to compare for equality using a method which looks like this:

bool AreEqual(MyObject O1, MyObject O2);

What would be the most performance friendly way of grouping all equal objects? The obvious answer would be to compare every object with all the other objects in the collection but this would rather hurt the performance ( N ^ N, I believe).

Could the LINQ group by operator offer a solution?

EDIT:

I should perhaps have named MyObject TheirObject as I cannot modify its implementation (and it doesn't implement IComparable). This means I'll probably use ICR's solution.

Answer 1

You don't need to compare every object to every other object, you need to compare every object with every group (e.g. the first item in the group) and create a new group if it doesn't match any (or if it's the first item).

The might look something like:

public static IEnumerable<IEnumerable<T>> Group<T>(IEnumerable<T> items)
    where T : IEquatable<T>
{
    IList<IList<T>> groups = new List<IList<T>>();

    foreach (T t in items)
    {
        bool foundGroup = false;

        foreach (IList<T> group in groups)
        {
            Debug.Assert(group.Count() >= 1);
            if (group[0].Equals(t))
            {
                group.Add(t);
                foundGroup = true;
                break;
            }
        }

        if (!foundGroup)
        {
            IList<T> newGroup = new List<T>() { t };
            groups.Add(newGroup);
        }
    }

    foreach (IList<T> group in groups)
    {
        yield return group;
    }
}

This is, of course, already done for you in Linq, which people have outlined above how to use. I just wanted to demonstrate that the algorithm can be a little better than comparing every item to every item.

N.B. The algorithm relies on the assumption that the equality relationship is transitive -- i.e. if a is equal to b, and b is equal to c, then a is equal to c. Though I'm not quite sure how you would group non-transitive items.

Answer 2

I would suggest using IComparable interface for MyObject class and then try grouping it, for example as it is done here or here