7
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I'm a little confused by your definitions. Would "abcd", "efg" and "hi" also satisfy your requirements? Also, need the output be lists or just enumerables? \$\endgroup\$ – dbc Aug 13 '14 at 7:29
  • \$\begingroup\$ @dbc I guess not, because efg is neither a subset of cehi 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\$ – vnp Aug 13 '14 at 7:35
  • \$\begingroup\$ 1) Move all duplicate elements to new sets in result. 2) Add remaining sets to result. I assume by "lists" you mean "sets" in that there are no duplicate elements within each "list"? You can't have "abacd" in the input list, right? \$\endgroup\$ – David Harkness Aug 13 '14 at 7:42
  • 1
    \$\begingroup\$ How about "Disjoint Subset Cover"? \$\endgroup\$ – Snowbody Aug 13 '14 at 20:25
  • 1
    \$\begingroup\$ @DavidHarkness for \$\left\{ a, b, c \right\}, \left\{ b, c \right\}\$ that would result in \$\left\{ a \right\}, \left\{ b \right\}, \left\{ c \right\}\$, instead of \$\left\{ a \right\}, \left\{ b, c \right\}\$. \$\endgroup\$ – mjolka Aug 14 '14 at 6:17
4
\$\begingroup\$

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)\$.

\$\endgroup\$
  • \$\begingroup\$ Thanks for spotting the bug. I was like "no way!", but then I added the test and you were right. \$\endgroup\$ – Andrew Shepherd Aug 13 '14 at 22:47
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think you could use GroupBy() to get rid of that foreach and lookup: sets.SelectMany(set => set).Distinct().GroupBy(e => GetContainingSets(e, sets)). \$\endgroup\$ – svick Aug 14 '14 at 9:59
  • \$\begingroup\$ Also, this should have the time complexity of \$\mathcal{O}(k \cdot n^2)\$, so it's improvement in that regard too. \$\endgroup\$ – svick Aug 14 '14 at 10:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.