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