Fast Data structure for finding strict subsets (from a given list)

algorithm, data-structures, performance, set

Solution

Mathematically, you should construct the Hasse diagram for your sets, which will be the partially ordered set with vertices your sets and arrows given by containment. Essentially, you want to create a directed, acyclic graph with an arrow `A --> B` if `A` strictly contains `B` and there is no `C` such that `A` strictly contains `C` and `C` strictly contains `B`.

This is actually going to be a ranked poset, meaning that you can keep track of "levels" of the digraph based on the cardinality of the sets. This is sort of like creating a hash table to jump to the right set.

From `A`, just do a BFS down the graph to find all proper subsets of `A`.

How to implement this: (in pseudocode)

for (C in sets) {
    for (B in HasseDiagram at rank rank(C)+1) {
      if (C contains B)
        addArrow(C,B)
    }
    for (A in HasseDiagram at rank rank(C)+1) {
      if (C contains A)
        addArrow(A,C)
    }
    addToDiagram(C)
}

To make this and all the subroutines fast, you can encode each set an a binary where digit `i` is `1` if `i` is in `C` and `0` otherwise. This makes testing containment and determining rank trivial.

The above method works if you have all possible subsets. Since you may be missing some, you'll have to check more things. For the pseudocode, you'll need to change `rank(C)-1` to the largest integer `l < rank(C)` such that some element of the HasseDiagram has rank `l`, and similarly for `rank(C)+1`. Then, when you're adding the set `C` to the diagram:

If `A` covers `C`, then you only need to check lower ranked sets `B` that are also covered by `A`.

If `C` covers `B`, then you only need to check higher ranked sets `A` that also cover by `B`.

By "`X` covers `Y`" I mean there is an arrow `X -> Y`, not just a path.

Furthermore, when you insert `C` between `A` and `B` using one of the above checks, you will need to remove the arrow `A --> B` when you add `A --> C` and `C --> B`.

Problem

I have a large set of sets e.g. `{{2,4,5} , {4,5}, ...}.` Given one of these subsets, I would like to iterate through all other subsets which are strict subsets of this subset. That is, if I am interested in set `A`, e.g. `{2,4,5}`, I want to find all sets `B` where the relative complement `B / A = {},` the empty set. Some possibilities could be `{2,4}`, `{2,5}` but not `{2,3}` I could of course search linearly and check each time, but am looking for an efficient data structure both for the larger set and the subset (if it matters). The number of subsets is typically in the 10s of thousands, but if it makes a difference I would be interested in cases where it could be in the hundreds of millions. The size of the subsets is typically in 10s. I am programming in C++ Thanks

Original source