1

I have a problem that I have encountered a number of times in practice, and I'm curious if there is a formal name for it so I can look for other people's solutions (I wrote an algorithm to solve it, but maybe it could be faster).

The problem is as follows: I have as input a set of sets $I$, and I want as output a set of sets $O$. This grouping has to be such that:

  1. Every element is only in one of the sets in $O$, i.e. for all $o, o' \in O$ we have $o \cap o' = \emptyset$ unless $o = o'$.

  2. Any element in a set in $I$ is in a set in $O$, i.e. for all $e \in i, i \in I$ there exists a set $o \in O$ s.t. $e \in o$.

  3. If items are in the same set $o \in O$, this means that for all sets $i \in I$, either $o \subseteq i$, or $o \cap i = \emptyset$.

  4. All sets $o \in O$ are maximal, i.e. the cardinality of $O$ is minimal.

As an example:

$I = \{\{1,2,3\},\{3,4,5\},\{1,2\}\}$

Yields:

$O = \{\{1,2\},\{3\},\{4,5\}\}$

This output would violate rule 4, but not 1, 2 or 3:

$O = \{\{1\},\{2\},\{3\},\{4\},\{5\}\}$

I would also be interested in algorithms that solve this problem quickly but not to optimality, i.e. with a small rather than minimal number of output sets.

Thanks.

Sam van Herwaarden
  • 227

2 Answers2

0

Actually, revisiting the problem like this gave me an idea to solve the problem (I think quite efficiently).

First, generate a matrix with one row for each distinct element occurring in any $i \in I$, and one column for each set in $I$.

Next, fill the matrix: for each row/column combination insert a 1 if the element corresponding to that row is in the set corresponding to that column. For the example problem from the question:

$\matrix{ 1 & 0 & 1\\ 1 & 0 & 1\\ 1 & 1 & 0\\ 0 & 1 & 0\\ 0 & 1 & 0}$

Finally, sort the rows in the matrix lexicographically. After this all elements that always occur together should correspond to rows that are next to each other in the matrix. It is then fairly straightforward to collect co-occurring elements. (In the case of the example I will skip the sort as it is not even necessary.)

Sam van Herwaarden
  • 227
0

And another algorithm for solving the problem, without the need of generating the whole matrix described in my other answer. In this approach, we start with a grouping where $O$ contains only one set, the union of all input sets. Then go through all input sets in sequence and refine the output grouping appropriately. In Haskell code:

import Data.List (foldl', intersect, nub, (\\))

prependIfNotEmpty :: [a] -> [[a]] -> [[a]]
prependIfNotEmpty [] l = l
prependIfNotEmpty p@(x:_) l = p:l

findClusters :: Eq a => [a] -> [[a]] -> [[a]]
findClusters items = foldl' go [items]
  where go clustering set = foldl' (go' set) [] clustering
        go' set processed cluster =
          prependIfNotEmpty (cluster \\ set) $
            prependIfNotEmpty (cluster `intersect` set) processed

findClusters' :: Eq a => [[a]] -> [[a]]
findClusters' sets = findClusters (nub $ concat sets) sets
Sam van Herwaarden
  • 227