I have a list of sets. The same items may appear in multiple sets.
I want to transform this into a new list of sets where:
- Each item only appears once in the entire list of sets.
- For each set in this new list, on every set in the old list, the new set will either be a subset or will not intersect at all.
I want this new list of sets to contain the minimum number of sets it can while still satisfying the above two requirements.
For example, this list
- abcd
- befg
- cehi
Would turn into
- ad
- b
- c
- e
- fg
- hi
This seems like a pretty generic problem. Is there a name for it?
Here's my implementation. It requires the comparison of each set with each other set, so I guess this has a performance \$O(k \cdot n^2)\$ where \$n\$ is the count of lists, and \$k\$ is the average length of each set.
Are there any efficiency issues that could be fixed easily?
public static class SetUtilities
{
public static IEnumerable<IEnumerable<T>> MinimumNonIntersectingSets<T>(this IEnumerable<IEnumerable<T>> sets)
{
List<List<T>> disjointSets = new List<List<T>>();
// Special case: if there is a null set we have to add it first
if (sets.Any(s => !(s.Any())))
{
disjointSets.Add(new List<T>());
sets = sets.Where(s => s.Any());
}
foreach (IEnumerable<T> newSet in sets)
{
List<T> disjointCopy = newSet.ToList();
int i = 0;
while(i < disjointSets.Count())
{
var intersection = disjointSets[i].Intersect(disjointCopy).ToList();
if ((intersection.Count() == disjointCopy.Count()) && (intersection.Count() == disjointSets[i].Count())) // They are equal
{
disjointCopy.Clear();
break;
}
if (intersection.Any())
{
disjointSets[i] = disjointSets[i].Except(intersection).ToList();
disjointSets.Insert(++i, intersection);
disjointCopy = disjointCopy.Except(intersection).ToList();
}
++i;
}
if(disjointCopy.Any())
{
disjointSets.Add(disjointCopy);
}
}
return disjointSets;
}
}
efg
is neither a subset ofcehi
nor is disjoint with it. However,[a, b, c, d, e, f, g, h, i]
seem to satisfy the requirements. Is there an additional requirement to minimize "new" list length? \$\endgroup\$