Linq OrderBy to group objects with the same sets

Question

I have a set of objects that themselves contain a set.

private class Pilot
{
    public string Name;
    public HashSet<string> Skills;
}

Here's some test data:

public void TestSetComparison()
{
    var pilots = new[] 
    {
        new Pilot { Name = "Smith", Skills = new HashSet<string>(new[] { "B-52", "F-14" }) },
        new Pilot { Name = "Higgins", Skills = new HashSet<string>(new[] { "Concorde", "F-14" }) },
        new Pilot { Name = "Jones", Skills = new HashSet<string>(new[] { "F-14", "B-52" }) },
        new Pilot { Name = "Wilson", Skills = new HashSet<string>(new[] { "F-14", "Concorde" }) },
        new Pilot { Name = "Celko", Skills = new HashSet<string>(new[] { "Piper Cub" }) },
    };

I want to use OrderBy in Linq so that:

• Smith and Jones are ordered together because they fly the same planes
• Higgins and Wilson are ordered together because they fly the same planes
• doesn't matter whether Higgins+Wilson end up before or after Smith+Jones
• preferably Smith is before Jones (stable sort) but this isn't too important

I think I need to implement an IComparer<Pilot> to pass into OrderBy but don't know how to handle the "doesn't matter" aspect (above) and the stable sort.

UPDATE:

I want the output to be an array of the same five Pilot objects but in a different order.

Answer 1

When GroupBy you have to implement IEqualityComparer<T> for the type you are going to group (HashSet<string> in your case), e.g.

private sealed class MyComparer : IEqualityComparer<HashSet<string>> {
  public bool Equals(HashSet<string> x, HashSet<string> y) {
    if (object.ReferenceEquals(x, y))
      return true;
    else if (null == x || null == y)
      return false;

    return x.SetEquals(y);
  }

  public int GetHashCode(HashSet<string> obj) {
    return obj == null ? -1 : obj.Count;
  }
}

And then use it:

 IEnumerable<Pilot> result = pilots
    .GroupBy(pilot => pilot.Skills, new MyComparer())
    .Select(chunk => string.Join(", ", chunk
       .Select(item => item.Name)
       .OrderBy(name => name))); // drop OrderBy if you want stable Smith, Jones

 Console.WriteLine(string.Join(Environment.NewLine, result));

Outcome:

 Jones, Smith
 Higgins, Wilson
 Celko

Edit: If you want an array reodered then add SelectMany() in order to flatten the groupings and the final ToArray():

 var result = pilots
    .GroupBy(pilot => pilot.Skills, new MyComparer())
    .SelectMany(chunk => chunk)
    .ToArray();

 Console.WriteLine(string.Join(", ", result.Select(p => p.Name)));

Outcome:

 Jones, Smith,
 Higgins, Wilson,
 Celko

Note that string.join combines the names of each group in one line, i.e. Jones, Smith both have the same skill set.

Run it as DotNetFiddle

Answer 2

You can use the following implementation of HashSetByItemsComparer to accomplish what you need:

public class HashSetByItemsComparer<TItem> : IComparer<HashSet<TItem>>
{
    private readonly IComparer<TItem> _itemComparer;

    public HashSetByItemsComparer(IComparer<TItem> itemComparer)
    {
        _itemComparer = itemComparer;
    }

    public int Compare(HashSet<TItem> x, HashSet<TItem> y)
    {
        foreach (var orderedItemPair in Enumerable.Zip(
            x.OrderBy(item => item, _itemComparer),
            y.OrderBy(item => item, _itemComparer), 
            (a, b) => (a, b))) //C# 7 syntax used - Tuples
        {
            var itemCompareResult = _itemComparer.Compare(orderedItemPair.a, orderedItemPair.b);
            if (itemCompareResult != 0)
            {
                return itemCompareResult;
            }
        }

        return 0;
    }
}

It is not the most efficient solution probably, since it orders hashsets for each comparison separately. You may need to optimize it if using with millions of pilots and many skills, but for small numbers it will work just fine.

Usage example:

var sortedPilots = pilots.OrderBy(p => p.Skills, new HashSetByItemsComparer<string>(StringComparer.Ordinal));

foreach (var pilot in sortedPilots)
{
    Console.WriteLine(pilot.Name);
}

And output is:

Smith
Jones
Higgins
Wilson
Celko

So it preserves equal items ordering (default behavior of OrderBy - you don't need to worry about it). By the way, solution with GroupBy would not allow you to restore items order as far as I know.