Convert a list of sets into the minimum list of non-intersecting sets

Question

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;
    }
}

Answer 1

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.

You shouldn't guess the time complexity, you should carefully analyze your code, so let's do that:

• The empty test check is \$\mathcal{O}(n)\$.

• The foreach is over all sets in the input, that's \$n\$.

• The while loop is over all sets in the output so far. The number of iterations will form something similar to arithmetic progression, with maximum at \$m\$, the number of sets in the output. The average is going to be \$\approx m/2\$, so this part is going to contribute \$\mathcal{O}(m)\$.

  (A formal proof would require proving that “something similar to arithmetic progression” will actually contribute that, but this is not a formal proof)

• Calculating intersection and complements of sets is going to be \$\mathcal{O}(k)\$.

• Inserting in the middle of a List of length \$\mathcal{O}(m)\$ is \$\mathcal{O}(m)\$.

Put together, we have \$\mathcal{O}(n + n \cdot m \cdot (k + m)) = \mathcal{O}(n \cdot m \cdot (k + m))\$.

That Insert annoyingly increases the complexity, but we can easily get rid of it either by using LinkedList (and walking it instead of using indexes) or by Adding at the end of the List (and making sure we don't iterate over the sets that were just added). This will bring us to \$\mathcal{O}(n \cdot m \cdot k)\$.

So, how big is \$m\$? Your estimate indicates you assumed it's \$\mathcal{O}(n)\$, but even your example shows that it can be larger than \$n\$. So, can it actually grow beyond \$\mathcal{O}(n)\$? Turns out, it can: when each of the \$n\$ sets has exactly one element in common with each other set*, then in the output, each of the \$n(n-1)/2\$ elements has to be in its own set, so the length of the output is \$\mathcal{O}(n^2)\$.

This means, that the total worst case complexity of your algorithm is \$\mathcal{O}(n^3 \cdot k)\$

* Or, in the language of graph theory, the sets are sets of incident edges for vertexes of a complete graph on \$n\$ vertices.

---

For some inputs, your output contains lots of empty sets that don't belong there. For example, try it on new[] { new[] { 1 }, new[] { 1, 2 }, new[] { 1, 2, 3 } }.

---

// Special case: if there is a null set we have to add it first

No, you don't need a special case for the empty set. It doesn't intersect with anything, so both your requirement will be still fulfilled, even if you don't include it in the output.

---

.Count()

I think it's better to use the Count property instead of the Count() extension method, to make it clear that it's an \$\mathcal{O}(1)\$ operation, not \$\mathcal{O}(n)\$.

Answer 2

The first observation is that we need only process distinct elements.

foreach (var e in sets.SelectMany(set => set).Distinct())
{
    ...
}

We now need to decide where each element e should go. Let's look at your example:

\begin{align} A &= \left\{ a, b, c, d \right\} \\ B &= \left\{ b, e, f, g \right\} \\ C &= \left\{ c, e, h, i \right\} \end{align}

The resulting sets are

\begin{array}{ c | c | c | c } & \in A & \in B & \in C \\ \hline a & \mbox{t} & \mbox{f} & \mbox{f} \\ d & \mbox{t} & \mbox{f} & \mbox{f} \\ \hline b & \mbox{t} & \mbox{t} & \mbox{f} \\ \hline c & \mbox{t} & \mbox{f} & \mbox{t} \\ \hline e & \mbox{f} & \mbox{t} & \mbox{t} \\ \hline f & \mbox{f} & \mbox{t} & \mbox{f} \\ g & \mbox{f} & \mbox{t} & \mbox{f} \\ \hline h & \mbox{f} & \mbox{f} & \mbox{t} \\ i & \mbox{f} & \mbox{f} & \mbox{t} \end{array}

So it seems we should put e into a new set based on its containment in each of the original sets. Let's use a binary string to represent this:

private static string GetContainingSets<T>(T element, IList<HashSet<T>> sets)
{
    var containingSets = new StringBuilder(sets.Count);
    foreach (var set in sets)
    {
        containingSets.Append(set.Contains(element) ? '1' : '0');
    }

    return containingSets.ToString();
}

And now we use a Dictionary to keep track of the sets as we create them

private static IEnumerable<HashSet<T>> MinimumNonIntersectingSets<T>(IList<HashSet<T>> sets)
{
    var lookup = new Dictionary<string, HashSet<T>>();
    foreach (var e in sets.SelectMany(set => set).Distinct())
    {
        var key = GetContainingSets(e, sets);
        HashSet<T> set;
        if (lookup.TryGetValue(key, out set))
        {
            set.Add(e);
        }
        else
        {
            lookup.Add(key, new HashSet<T> { e });
        }
    }

    return lookup.Values;
}

"Proof" of correctness

Each item only appears once in the entire list of sets.

Each distinct element in the union of the sets is added to exactly one set in the output.

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.

This is guaranteed by the binary strings used to label the sets.

I want this new list of sets to contain the minimum number of sets it can while still satisfying the above two requirements.

Any solution satisfying the above requirement would consist of sets of elements that each have the same binary string label used in this algorithm. Since each set in this solution is maximal in regards to its binary string label, the resulting solution is minimal.