How do I compare items from a list to all others without repetition?

Question

I have a collection of objects (lets call them MyItem) and each MyItem has a method called IsCompatibleWith which returns a boolean saying whether it's compatible with another MyItem.

public class MyItem
{
    ...
    public bool IsCompatibleWith(MyItem other) { ... }
    ...
}

A.IsCompatibleWith(B) will always be the same as B.IsCompatibleWith(A). If for example I have a collection containing 4 of these, I am trying to find a LINQ query that will run the method on each distinct pair of items in the same collection. So if my collection contains A, B, C and D I wish to do the equivalent of:

A.IsCompatibleWith(B); // A & B
A.IsCompatibleWith(C); // A & C
A.IsCompatibleWith(D); // A & D
B.IsCompatibleWith(C); // B & C
B.IsCompatibleWith(D); // B & D
C.IsCompatibleWith(D); // C & D

The code initially used was:

var result = from item in myItems
             from other in myItems
             where item != other && 
                   item.IsCompatibleWith(other)
             select item;

but of course this will still do both A & B and B & A (which is not required and not efficient). Also it's probably worth noting that in reality these lists will be a lot bigger than 4 items, hence the desire for an optimal solution.

Hopefully this makes sense... any ideas?

Edit: One possible query -

MyItem[] items = myItems.ToArray();
bool compatible = (from item in items
                   from other in items
                   where
                       Array.IndexOf(items, item) < Array.IndexOf(items, other) &&
                       !item.IsCompatibleWith(other)
                   select item).FirstOrDefault() == null;

Edit2: In the end switched to using the custom solution from LukeH as it was more efficient for bigger lists.

public bool AreAllCompatible()
{
    using (var e = myItems.GetEnumerator())
    {
        var buffer = new List<MyItem>();
        while (e.MoveNext())
        {
            if (buffer.Any(item => !item.IsCompatibleWith(e.Current)))
                return false;
            buffer.Add(e.Current);
        }
    }
    return true;
}

Answer 1

Edit...

Judging by the "final query" added to your question, you need a method to determine if all the items in the collection are compatible with each other. Here's how to do it reasonably efficiently:

bool compatible = myItems.AreAllItemsCompatible();

// ...

public static bool AreAllItemsCompatible(this IEnumerable<MyItem> source)
{
    using (var e = source.GetEnumerator())
    {
        var buffer = new List<MyItem>();

        while (e.MoveNext())
        {
            foreach (MyItem item in buffer)
            {
                if (!item.IsCompatibleWith(e.Current))
                    return false;
            }
            buffer.Add(e.Current);
        }
    }
    return true;
}

Original Answer...

I don't think there's an efficient way to do this using only the built-in LINQ methods.

It's easy enough to build your own though. Here's an example of the sort of code you'll need. I'm not sure exactly what results you're trying to return so I'm just writing a message to the console for each compatible pair. It should be easy enough to change it to yield the results that you need.

using (var e = myItems.GetEnumerator())
{
    var buffer = new List<MyItem>();

    while (e.MoveNext())
    {
        foreach (MyItem item in buffer)
        {
            if (item.IsCompatibleWith(e.Current))
            {
                Console.WriteLine(item + " is compatible with " + e.Current);
            }
        }
        buffer.Add(e.Current);
    }
}

(Note that although this is reasonably efficient, it does not preserve the original ordering of the collection. Is that an issue in your situation?)