Set of maximal independent subsets via a c# generator

Question

I want to find all subsets of a given set that are mutually exclusive and contain as many elements of the superset as possible. Where the user defines a meaning for exclusiveness:

bool exclusion<T>(T a, T b)

where at least exclusion(a, b) == exclusion(b, a) holds.

And exclusion(a, b) == true is guaranteed if a.Equals(b) == true

My code looks like this:

public static HashSet<HashSet<T>> MutuallyExclusive<T>(this IEnumerable<T> available, Func<T, T, bool> exclusion) {
    HashSet<HashSet<T>> finished = new HashSet<HashSet<T>>(new HashSetEquality<T>());
    Recursion<T>(available, new HashSet<T>(), finished, exclusion);
    return finished;
}

private static void Recursion<T>(IEnumerable<T> available, HashSet<T> accepted, HashSet<HashSet<T>> finished, Func<T, T, bool> exclusion) {
    if (!available.Any())
        finished.Add(accepted);
    else
        foreach (T a in available)
            Recursion<T>(available.Where(b => !exclusion(a, b)), new HashSet<T>(accepted) { a }, finished, exclusion);
}

private class HashSetEquality<T> : IEqualityComparer<HashSet<T>> {
    public bool Equals(HashSet<T> x, HashSet<T> y) {
        if (x.Count != y.Count)
            return false;
        return x.All(t => y.Contains(t));
    }

    public int GetHashCode(HashSet<T> obj) {
        return obj.Aggregate(0, (i, t) => i ^ t.GetHashCode());
    }
}

Is there a way to turn this code into an iterator moving through the accepted values one by one?

Edit:

It seems I was I little unprecise in my question, sorry. I was actually searching for a Generator for deffered execution. So that every time you call it only the next accepted set is calculated

Answer 1

Basically, what you want to do is to yield a new set every time you call finished.Add() and it returns true.

But because of the recursion, you also need to yield all values returned from the recursive calls. You can do that by yielding all those values in a loop:

public static IEnumerable<HashSet<T>> MutuallyExclusive<T>(
    this IEnumerable<T> available, Func<T, T, bool> exclusion)
{
    var finished = new HashSet<HashSet<T>>(new HashSetEquality<T>());
    return Recursion<T>(available, new HashSet<T>(), finished, exclusion);
}

private static IEnumerable<HashSet<T>> Recursion<T>(
    IEnumerable<T> available, HashSet<T> accepted, HashSet<HashSet<T>> finished,
    Func<T, T, bool> exclusion)
{
    if (!available.Any())
    {
        if (finished.Add(accepted))
            yield return finished;
    }
    else
        foreach (T a in available)
        {
            var results = Recursion<T>(
                available.Where(b => !exclusion(a, b)),
                new HashSet<T>(accepted) { a }, finished, exclusion);

            foreach (var set in results)
                yield return set;
        }
}

It's probably not the most efficient solution, but it gets the job done.

Also, you might want to consider going through every subset only once. That way, you wouldn't need the finished set and you could directly yield all results you find.